Geodesic
Cospectral Pairs of Regular Graphs with Different Connectivity
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 577-584.

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

For vertex- and edge-connectivity we construct infinitely many pairs of regular graphs with the same spectrum, but with different connectivity.
Keywords: graph spectrum, vertex-connectivity, edge-connectivity, spectral characterization 
@article{DMGT_2020_40_2_a12,
     author = {Haemers, Willem H.},
     title = {Cospectral {Pairs} of {Regular} {Graphs} with {Different} {Connectivity}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {577--584},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a12/}
}
TY  - JOUR
AU  - Haemers, Willem H.
TI  - Cospectral Pairs of Regular Graphs with Different Connectivity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 577
EP  - 584
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a12/
LA  - en
ID  - DMGT_2020_40_2_a12
ER  - 
%0 Journal Article
%A Haemers, Willem H.
%T Cospectral Pairs of Regular Graphs with Different Connectivity
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 577-584
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a12/
%G en
%F DMGT_2020_40_2_a12
Haemers, Willem H. Cospectral Pairs of Regular Graphs with Different Connectivity. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 577-584. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a12/

[1] A. Abiad, B. Brimkov, X. Martínez-Rivera, J. Zhang and S. O, Spectral bounds for the connectivity of regular graphs of given order, Electron. J. Linear Algebra 34 (2018) 428–443. doi:10.13001/1081-3810.3675

[2] Z. Blázsik, J. Cummings and W.H. Haemers, Cospectral regular graphs with and without a perfect matching, Discrete Math. 338 (2015) 199–201. doi:10.1016/j.disc.2014.11.002

[3] A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, 2012). doi:10.1007/978-1-4614-1939-6

[4] S.M. Cioabă, Eigenvalues and edge-connectivity of regular graphs, Linear Algebra Appl. 432 (2010) 458–470. doi:10.1016/j.laa.2009.08.029

[5] D.M. Cvetković, P. Rowlinson and S.K. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2009). doi:10.1017/CBO9780511801518

[6] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298–305.

[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, Distance-regularity and the spectrum of graphs, Linear Algebra Appl. 236 (1996) 265–278. doi:10.1016/0024-3795(94)00166-9

[9] W.H. Haemers and E. Spence, Graphs cospectral with distance-regular graphs, Linear Multilinear Algebra 39 (1995) 91–107. doi:10.1080/03081089508818382

[10] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (Springer-Verlag, Berlin, 2003).

[11] D. Stevanović, V. Brankov, D.M. Cvetković and S. Simić, newGRAPH. http://www.mi.sanu.ac.rs/newgraph/index.html