On ±1 eigenvectors of graphs

Authors

  • Dragan Stevanović University of Primorska

DOI:

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

Keywords:

Eigenvector, adjacency matrix, Wilf's problem

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.

Published

2016-09-26

Issue

Section

Mathematical Chemistry Issue - In Memory of Ante Graovac