DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

L.K. Pinheiro, B.S. Souza, V. Trevisan

Title:

Determining graphs by the complementary spectrum

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-06-26, Revised: 2019-09-22, Accepted: 2019-10-14, https://doi.org/10.7151/dmgt.2280

Abstract:

The complementary spectrum of a connected graph $G$ is the set of the complementary eigenvalues of the adjacency matrix of $G$. In this note, we discuss the possibility of representing $G$ using this spectrum. On one hand, we give evidence that this spectrum distinguishes more graphs than other standard graph spectra. On the other hand, we show that it is hard to compute the complementary spectrum. In particular, we see that computing the complementary spectrum is equivalent to finding all connected induced subgraphs.

Keywords:

graphs, complementary eigenvalues, graph isomorphism

PDF
Close