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/

[1] F. Belardo, On the structure of bidegreed graphs with minimal spectral radius, Filomat 28 (2014) 1–10. doi:10.2298/FIL1401001B

[2] J.A. Carvalho, B.S. Souza, V. Trevisan and F.C. Tura, Exponentially many graphs have a Q-cospectral mate, Discrete Math. 340 (2017) 2079–2085. doi:10.1016/j.disc.2017.04.009

[3] D. Cvetković and S.K. Simić, Towards a spectral theory of graphs based on the signless Laplacian I, Publ. Inst. Math. (Beograd) (N.S.) 85(99) (2009) 19–33. doi:10.2298/PIM0999019C

[4] D. Cvetković and S.K. Simić, Towards a spectral theory of graphs based on the signless Laplacian. II, Linear Algebra Appl. 432 (2010) 2257–2272. doi:10.1016/j.laa.2009.05.020

[5] D. Cvetković and S.K. Simić, Towards a spectral theory of graphs based on the signless Laplacian III, Appl. Anal. Discrete Math. 4 (2010) 156–166. doi:10.2298/AADM1000001C

[6] R. Fernandes, J. Judice and V. Trevisan, Complementary eigenvalues of graphs, Linear Algebra Appl. 527 (2017) 216–231. doi:10.1016/j.laa.2017.03.029

[7] C.D. Godsil and B.D. McKay, Constructing cospectral graphs, Aequationes Math. 25 (1982) 257–268. doi:10.1007/BF02189621

[8] W.H. Haemers, Are almost all graphs determined by their spectrum ?, Not. S. Afr. Math. Soc. 47 (2016) 42–45.

[9] A.J. Hoffman and J.H. Smith, On the spectral radii of topologically equivalent graphs, in: Proc. Second Czechoslovak Sympos., Prague, 1974, Recent Advances in Graph Theory (Academia, Prague, 1975) 273–281.

[10] B.D. McKay, On the spectral characterisation of trees, Ars Combin. 3 (1977) 219–232.

[11] E.R. Oliveira, D. Stevanović and V. Trevisan, Spectral radius ordering of starlike trees, Linear Multilinear Algebra (2018), in press. doi:10.1080/03081087.2018.1524435

[12] A.J. Schwenk, Almost all trees are cospectral, in: Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971, New Directions in the Theory of Graphs (Academic Press, New York, 1973) 275–307.

[13] A. Seeger, Complementarity eigenvalue analysis of connected graphs, Linear Algebra Appl. 543 (2018) 205–225. doi:10.1016/j.laa.2017.12.021

[14] E.R. van Dam and W.H. Haemers, Which graphs are determined by their spectrum ?, Linear Algebra Appl. 373 (2003) 241–272. doi:10.1016/S0024-3795(03)00483-X

[15] E.R. van Dam and W.H. Haemers, Developments on spectral characterizations of graphs, Discrete Math. 309 (2009) 576–586. doi:10.1016/j.disc.2008.08.019