Geodesic
On the Spectral Characterizations of Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 729-744.

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

Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question “Which graphs are determined by their spectrum?” is still a difficult problem in spectral graph theory. Let 𝒰_p^2q be the set of graphs obtained from C_p by attaching two pendant edges to each of q (q ≤ p) vertices on C_p, whereas 𝒱_p^2q the subset of 𝒰_p^2q with odd p and its q vertices of degree 4 being nonadjacent to each other. In this paper, we show that each graph in 𝒰_p^2q, p even and its q vertices of degree 4 being consecutive, is determined by its Laplacian spectrum. As well we show that if G is a graph without isolated vertices and adjacency cospectral with the graph in 𝒱_p^p−1 = { H }, then G ≅ H.
Keywords: Laplacian spectrum, adjacency spectrum, cospectral graphs, spectral characterization 
@article{DMGT_2017_37_3_a15,
     author = {Huang, Jing and Li, Shuchao},
     title = {On the {Spectral} {Characterizations} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {729--744},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a15/}
}
TY  - JOUR
AU  - Huang, Jing
AU  - Li, Shuchao
TI  - On the Spectral Characterizations of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 729
EP  - 744
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a15/
LA  - en
ID  - DMGT_2017_37_3_a15
ER  - 
%0 Journal Article
%A Huang, Jing
%A Li, Shuchao
%T On the Spectral Characterizations of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 729-744
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a15/
%G en
%F DMGT_2017_37_3_a15
Huang, Jing; Li, Shuchao. On the Spectral Characterizations of Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 729-744. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a15/

[1] S. Barik, S. Patiand and B.K. Sarma, The spectrum of the corona of two graphs, SIAM J. Discrete Math. 21 (2007) 47–56. doi:10.1137/050624029

[2] J.A. Bondy and U.S.R. Murty, Graph Theory, in: Graduate Texts in Mathematics, 244 (Springer, 2008).

[3] R. Boulet, Spectral characterization of sun graphs and broken sun graphs, Discrete Math. Theor. Comput. Sci. 11 (2009) 149–160.

[4] C.J. Bu and J. Zhou, Laplacian spectra characterization of some graphs obtained by product operation, Discrete Math. 312 (2012) 1591–1595. doi:10.1016/j.disc.2012.02.002

[5] C.J. Bu, J. Zhou, H.B. Li and W.Z. Wang, Spectral characterization of the corona of a cycle and two isolated vertices, Graphs Combin. 30 (2014) 1123–1133. doi:10.1007/s00373-013-1327-7

[6] L. Collatz and U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Semin. Univ. Hambg. 21 (1957) 63–77. doi:10.1007/BF02941924

[7] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications (Academic Press, New York, San Francisco, London, 1980).

[8] D. Cvetković and P. Rowlinson, Spectra of unicyclic graphs, Graphs Combin. 3 (1987) 7–23. doi:10.1007/BF01788525

[9] M. Cámara and W.H. Haemers, Spectral characterizations of almost complete graphs, Discrete Appl. Math. 176 (2014) 19–23. doi:10.1016/j.dam.2013.08.002

[10] 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

[11] M. Doob, Eigenvalues of graphs, in: L.W. Beineke, R.J. Wilson (Eds.), Topics in Algebraic Graph Theory (Cambridge University Press, 2005).

[12] O. Favaron, M. Mahéo, and J.F. Saclé, Some eigenvalues properties in graphs, Discrete Math. 111 (1993) 197–200. doi:10.1016/0012-365X(93)90156-N

[13] N. Ghareghai, G.R. Omidi and B. Tayfeh-Rezaie, Spectral characterization of graphs with index at most $ \sqrt{ 2 + \sqrt{5} } $, Linear Algebra Appl. 420 (2007) 483–489. doi:10.1016/j.laa.2006.08.009

[14] C. Godsil and G. Royle, Algebraic Graph Theory (Springer, 2001). doi:10.1007/978-1-4613-0163-9

[15] A.K. Kelmans and V.M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, J. Combin. Theory Ser. B 16 (1974) 197–214. doi:10.1016/0095-8956(74)90065-3

[16] J.S. Li and X.D. Zhang, On the Laplacian eigenvalues of a graph, Linear Algebra Appl. 285 (1998) 305–307. doi:10.1016/S0024-3795(98)10149-0

[17] F.J. Liu, Q.X. Huang, J.F. Wang and Q.H. Liu, The spectral characterization of ∞-graphs, Linear Algebra Appl. 437 (2012) 1482–1502. doi:10.1016/j.laa.2012.04.013

[18] M. Mirzakhah and D. Kiani, The sun graph is determined by its signless Laplacian spectrum, Electron. J. Linear Algebra. 20 (2010) 610–620. doi:10.13001/1081-3810.1397

[19] G.R. Omidi and K. Tajbakhsh, Starlike trees are determined by their Laplacian spectrum, Linear Algebra Appl. 422 (2007) 654–658. doi:10.1016/j.laa.2006.11.028

[20] V.M. Piet, Graph Spectra for Complex Networks (Cambridge University Press, 2010).

[21] X.L. Shen, Y.P. Hou and Y.P. Zhang, Graph Zn and some graphs related to Zn are determined by their spectrum, Linear Algebra Appl. 404 (2005) 58–68. doi:10.1016/j.laa.2005.01.036

[22] W. Wang and C.X. Xu, On the spectral characterization of T-shape trees, Linear Algebra Appl. 414 (2006) 492–501. doi:10.1016/j.laa.2005.10.031

[23] W. Wang and C.X. Xu, The T-shape tree is determined by its Laplacian spectrum, Linear Algebra Appl. 419 (2006) 78–81. doi:10.1016/j.laa.2006.04.005