On NP-hard graph properties characterized by the spectrum

Omid Etesami, Willem H. Haemers*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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 k≥6 we construct a pair of k-regular cospectral graphs, where one graph is Hamiltonian and the other one not.
Original languageEnglish
Pages (from-to)526-529
JournalDiscrete Applied Mathematics
Volume285
DOIs
Publication statusPublished - 15 Oct 2020

Keywords

  • Computational complexity
  • Cospectral graphs
  • Hamiltonian graph
  • Latin square
  • NP-hard problem
  • Spectral characterization

Fingerprint Dive into the research topics of 'On NP-hard graph properties characterized by the spectrum'. Together they form a unique fingerprint.

  • Cite this