“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16339
School of Mathematics
  Title:   On NP-hard graph properties characterized by the spectrum
  Author(s):  Omid Etesami (Joint with W. H. Haemers)
  Status:   Published
  Journal: Discrete Appl. Math.
  Vol.:  285
  Year:  2020
  Pages:   526-529
  Supported by:  IPM
  Abstract:
Properties of graphs that can be characterized by the spectrum of the adjacency matrix of the graph have been studied systematically recently. Motivated by the complexity of these properties, we show that there are such properties for which testing whether a graph has that property can be NP-hard (or belong to other computational complexity classes consisting of even harder problems). In addition, we discuss a possible spectral characterization of some well-known NP-hard properties. In particular, for every integer we construct a pair of -regular cospectral graphs, where one graph is Hamiltonian and the other one not.

Download TeX format
back to top
scroll left or right