On ±1 eigenvectors of graphs
DOI:
https://doi.org/10.26493/1855-3974.1021.c0aKeywords:
Eigenvector, adjacency matrix, Wilf's problemAbstract
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.
Downloads
Additional Files
Published
2016-09-26
Issue
Section
Mathematical Chemistry Issue - In Memory of Ante Graovac
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/