Geodesic
Determining Graphs by the Complementary Spectrum
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 607-620

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2020_40_2_a15,
     author = {Pinheiro, Luc\'elia K. and Souza, Bruna S. and Trevisan, Vilmar},
     title = {Determining {Graphs} by the {Complementary} {Spectrum}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {607--620},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a15/}
}
TY  - JOUR
AU  - Pinheiro, Lucélia K.
AU  - Souza, Bruna S.
AU  - Trevisan, Vilmar
TI  - Determining Graphs by the Complementary Spectrum
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 607
EP  - 620
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a15/
LA  - en
ID  - DMGT_2020_40_2_a15
ER  - 
%0 Journal Article
%A Pinheiro, Lucélia K.
%A Souza, Bruna S.
%A Trevisan, Vilmar
%T Determining Graphs by the Complementary Spectrum
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 607-620
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a15/
%G en
%F DMGT_2020_40_2_a15
Pinheiro, Lucélia K.; Souza, Bruna S.; Trevisan, Vilmar. Determining Graphs by the Complementary Spectrum. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 607-620. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a15/