On NP-Hard Graph Properties Characterized by the Spectrum

Omid Etesami, Willem H. Haemers

Research output: Working paperOther research output

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 problems. In particular, for every integer $k\geq 6$ we construct a pair of $k$-regular cospectral graphs, where one graph is Hamiltonian and the other one not.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages6
Publication statusPublished - 15 Dec 2019

Publication series

NamearXiv
Volume1912.07061

    Fingerprint

Keywords

  • math.CO
  • 05C50, 05C45, 68Q17

Cite this

Etesami, O., & Haemers, W. H. (2019). On NP-Hard Graph Properties Characterized by the Spectrum. (arXiv; Vol. 1912.07061). Ithaca: Cornell University Library.