On NP-hard graph properties characterized by the spectrum

Omid Etesami; Willem H. Haemers

doi:10.1016/j.dam.2020.06.020

On NP-hard graph properties characterized by the spectrum

Omid Etesami, Willem H. Haemers^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

5 Citations (Scopus)

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 language	English
Pages (from-to)	526-529
Journal	Discrete Applied Mathematics
Volume	285
DOIs	https://doi.org/10.1016/j.dam.2020.06.020
Publication status	Published - 15 Oct 2020

Keywords

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

Access to Document

10.1016/j.dam.2020.06.020

Cite this

@article{52183bdf1d1149d382f53261e487a95a,

title = "On NP-hard graph properties characterized by the spectrum",

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.",

keywords = "Computational complexity, Cospectral graphs, Hamiltonian graph, Latin square, NP-hard problem, Spectral characterization",

author = "Omid Etesami and Haemers, {Willem H.}",

year = "2020",

month = oct,

day = "15",

doi = "10.1016/j.dam.2020.06.020",

language = "English",

volume = "285",

pages = "526--529",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On NP-hard graph properties characterized by the spectrum

AU - Etesami, Omid

AU - Haemers, Willem H.

PY - 2020/10/15

Y1 - 2020/10/15

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Cospectral graphs

KW - Hamiltonian graph

KW - Latin square

KW - NP-hard problem

KW - Spectral characterization

UR - http://www.scopus.com/inward/record.url?scp=85087338050&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.06.020

DO - 10.1016/j.dam.2020.06.020

M3 - Article

AN - SCOPUS:85087338050

SN - 0166-218X

VL - 285

SP - 526

EP - 529

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

On NP-hard graph properties characterized by the spectrum

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this