On ±1 eigenvectors of graphs

Dragan Stevanović

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.


Keywords


Eigenvector, adjacency matrix, Wilf's problem

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.1021.c0a

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications