On ±1 eigenvectors of graphs

Abstract

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.