On plus/minus 1 eigenvectors of graphs - Stevanović, Dragan (Ars mathematica contemporanea, 2016)
While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph admits an eigenvector consisting solely of ?$± 1$? entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a ?$± 1$? eigenvector is quite rich, being closed under a number of different graph compositions.
Keywords: adjacency matrix; eigenvector; lastni vektorji; matrika sosednosti; Wilfov problem; Wilf's problem