GRAPHS WHICH ARE DETERMINED BY THEIR SPECTRUM

Year 2016, Volume: 4 Issue: 2, 34 - 41, 01.10.2016

ALI ZEYDI Abdıan

Abstract

It is well-known that the problem of spectral characterization is related to the H\"uckel theory from Chemistry. E. R. van Dam and W. H. Haemers $ [11] $ conjectured almost all graphs are determined by their spectra. Nevertheless, the set of graphs which are known to be determined by their spectra is small. Hence discovering infinite classes of graphs that are determined by their spectra can be an interesting problem and helps reinforce this conjecture. The main aim of this work is to characterize new classes of graphs that are known as multicone graphs. In this work, it is shown that any graph cospectral with multicone graphs $ K_w\bigtriangledown GQ(2,1) $ or $ K_w\bigtriangledown GQ(2,2) $ is determined by its adjacency spectra, where $ GQ(2,1) $ and $ GQ(2,2) $ denote the strongly regular graphs that are known as the generalized quadrangle graphs. Also, we prove that these graphs are determined by their Laplacian spectrum. Moreover, we propose four conjectures for further reseache in this topic.

Keywords

Adjacency spectrum, Laplacian spectrum, Determined by their spectra, generalized quadrangle

References

• [1] Abdian A.Z. and Mirafzal S.M., On new classes of multicone graphs determined by their spectrums, Alg. Struc. Appl, 2 (2015), no. 1, 21-32.
• [2] Abdollahi A., Janbaz S. and Oubodi M., Graphs cospectral with a friendship graph or its complement, Trans. Comb., 2 (2013), no. 4, 37-52.
• [3] Biggs N. L., Algebraic Graph Theory, Cambridge university press, 1993.
• [4] Cvetkovic D., Rowlinson P. and Simic S. , An introduction to the theory of graph spectra, London Mathematical Society Student Texts, 75, Cambridge University Press, 2010.
• [5] Das. K. C., Proof of conjectures on adjacency eigenvalues of graphs, Disceret Math, 313 (2013) , no. 1, 19{25.
• [6] Godsil C. D. and Royle G., Algebraic graph theory, Graduate Texts in Mathematics 207, 2001.
• [7] Knauer U., Algebraic graph theory: morphisms, monoids and matrices, 41, Walter de Gruyter, 2011.
• [8] Mohammadian A., Tayfeh-Rezaie B., Graphs with four distinct Laplacian eigenvalues, J. Algebraic Combin., 34 (2011), no. 4, 671{682.
• [9] Omidi G. R., On graphs with largest Laplacian eignnvalues at most 4, Australas. J. Combin., 44 (2009) 163{170.
• [10] Rowlinson P., The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math., 1 (2007) 445-471.
• [11] van Dam E. R. and Haemers W. H., Which graphs are determined by their spectrum?, Linear Algebra. Appl., 373 (2003) 241{272.
• [12] van Dam E. R., Haemers W. H., Developments on spectral characterizations of graphs, Discrete Math., 309 (2009), no.3, 576{586.
• [13] Wang J., Zhao H., and Huang Q., Spectral charactrization of multicone graphs, Czech. Math. J., 62 (2012), no.1, 117{126.
• [14] Wang J., Belardo F., Huang Q., and Borovicanin B., On the two largest Q-eigenvalues of graphs, Discrete Math., 310 (2010), no. 1, 2858{2866.
• [15] West D. B., Introduction to graph theory, Upper Saddle River: Prentice hall; 2001.