1.
On [plus/minus] 1 eigenvectors of graphsDragan Stevanović, 2016, original scientific article
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 ▫$\pm 1$▫ entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a ▫$\pm 1$▫ eigenvector is quite rich, being closed under a number of different graph compositions.
Keywords: eigenvector, adjacency matrix, Wilf's problem
Published in RUP: 03.01.2022; Views: 735; Downloads: 26
Full text (325,02 KB)