On new classes of multicone graphs determined by their spectrums

Document Type : Research Paper


Lorestan University


A multicone graph is defined to be join of a clique and a regular graph. A graph $ G $ is cospectral with graph $ H $ if their adjacency matrices have the same eigenvalues. A graph $ G $ is said to be determined by its spectrum or DS for short, if for any graph $ H $ with $ Spec(G)=Spec(H)$, we conclude that $ G $ is isomorphic to $ H $. In this paper, we present new classes of multicone graphs that are DS with respect to their spectrums. Also, we show that complement of these graphs are DS with respect to their adjacency spectrums. In addition, we show that graphs cospectral with these graphs are perfect. Finally, we find automorphism group of these graphs and one conjecture for further researches is proposed.


[1] A. Abdollahi, S. Janbaz and M. Oubodi, Graphs Cospectral with A Friendship Graph Or its Complement, Trans. Combin. Vol. 2 No. 4 (2013), pp. 37–52.
[2] N. L. Biggs, Algebraic Graph Theory, (second edition), Cambridge University press, cambridge, (1933). [3] X. M. Cheng, G. R. W. Greaves, J. H. Koolen, Graphs with three eigenvalues and second largest eigenvalue at most 1, http://de.arxiv.org/abs/1506.02435v1.
[4] D. Cvetkovi´c, P. Rowlinson and S. Simi´c, An Introduction to the theory of graph spectra, London Mathematical Society Student Texts, 75, Cambridge University Press, Cambridge, 2010.
[5] J. D. Dixon and B. Mortimer, Permutation Groups, Math. Proc. Cambridge Phil. Soc. (1998).
[6] G. H. Fath-Tabar, The Automorphism Group Of Finite Graphs, Iran. J. Math. Sci. Inf., (2007), 29–33.
[7] A. Ganasem, Automorphism groups of graphs, ArXiv: 1206. 6279v1 (2012).
[8] A. Ganasem, Automorphism of Cayley graph generated by transposition sets, arXiv 1303.5974v2.
[9] C. D. Godsil, On the full automorphism group of a graph, Combinatorica, 1 (1981) 243–256.
[10] C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001
 [11] U. Kanauer, Algebraic Graph Theory, Morphism, Monoids and Matrices, (2011).
[12] B. Liu, On an upper bound of the spectral radius of graphs, Discrete Mathematics 308 (2008) 5317–5324.
[13] R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl. 278 (1998), 221–236.
[14] A. Mohammadian, B. Tayfeh Rezaie, Graphs with four distinct Laplacian eigenvalues, J. Algebraic Combin. 34 (2011), 671–682.
[15] G. R. Omidi, On graphs with largest Laplacian eignnvalues at most 4, Australas. J. Combin., 44 (2009) 163–170.
[16] E. R. van Dam and W. H. Haemers, Which Graphs are determined by their spectrum?, Linear Alg. Appl. 373 (2003) 241–272.
[17] E. R. van Dam, Willem H. Haemers, Developments on spectral characterizations of graphs, Discrete Math., 309 (2009) 576–586.
[18] J. F. Wang, H. Zhao ,Q. Haung , Spectral Charactrization of Multicone Graphs. Czec. Math. J., 62 137 (2012), 117–126. 32
[19] J. Wang, Q. Huang, Spectral Characterization of Generalized Cocktail-Party Graphs. J. Math. Research Appl., (2012), Vol. 32, No. 6, pp. 666–672.
[20] D.B. West, Introduction to Graph Theory (Second Edition), University of Illinios—Urbana (2001)