On $\pm 1$-eigenvectors of graphs

Dragan Stevanovi\'c
Mathematical Institute, Serbian Academy of Sciences and Arts and University of Primorska, Slovenia



Content: While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph can have an eigenvector consisting solely of $\pm 1$ entries? This question reappeared independently more than twenty years later while we were studying Jerry Ray Dias' question on the existence of graphs with square roots of positive integers as their eigenvalues. We show that to answer Wilf's problem it is enough to be able to answer whether a graph has a $\pm 1$ eigenvector corresponding to the eigenvalue $0$. The latter problem, however, turns out to be NP-complete. In addition, Wilf's problem has different answers for the triangular graph $L(K_8)$ and the three Chang graphs cospectral to it, leaving little hope for a simple answer in general. Nevertheless, the set of graphs with a $\pm 1$ eigenvector corresponding to the eigenvalue $0$ turns out to be very rich, being closed under a number of different graph compositions.

Back to all abstracts