GRAPHS COSPECTRAL WITH MULTICONE GRAPHS Kw 5 L P

Abstract

E. R. van Dam and W. H. Haemers [15] conjectured that 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 innite classes of graphs that are determined by their spectra can be an interesting problem. The aim of this paper is to characterize new classes of multicone graphs that are determined by their spectrum. A multicone graph is dened to be the join of a clique and a regular graph. It is proved that any graph cospectral with multicone graph Kw 5 L P is determined by its adjacency spectrum as well as its Laplacian spectrum, where Kw and L P denote a complete graph on w vertices and the line graph of the Petersen graph, respectively. Finally, three problems for further researches are proposed.

Keywords

• adjacency spectrum,Laplacian spectrum,DS graph,line graph of Petersen graph.

References

1. [1] Abdian,A.Z. and Mirafzal,S.M., (2015), On new classes of multicone graphs determined by their spectrums, Alg. Struc. Appl., 2, pp.23-34.
2. [2] Abdollahi,A., Janbaz,S., and Oubodi,M., (2013), Graphs cospectral with a friendship graph or its complement, Trans. Comb., 2, pp.37-52.
3. [3] Bapat,R.B., (2010), Graphs and matrices, New York (NY), Springer.
4. [4] Biggs,N.L., (1933), Algebraic Graph Theory, Cambridge university press.
5. [5] Cvetkovi´c,D., Rowlinson,P., and Simi´c,S., (2010), An Introduction to the Theory of graph Spectra, London Mathematical Society Student Texts, 75, Cambridge University Press.
6. [6] Das,K.C., (2013), Proof of conjectures on adjacency eigenvalues of graphs, Disceret Math, 313 pp.19- 25.
7. [7] Godsil,C.D. and McKay,B.D., (1982), Constructing cospectral graphs, Aequationes Math., 25, pp.252- 268.
8. [8] G¨unthard,Hs.H. and Primas,H., (1956), Zusammenhang von Graphtheorie und Mo-Theorie vonMolekeln mit Systemen konjugierter Bindungen., Helv. Chim. Acta, 39, pp.1645-1653.

9. [9] Haemers,W.H. and Spence,E., (2004), Enumeration of cospectral graphs, Eur. J. Comb., 25 pp.199211.
10. [10] Harary,F., King,C., Mowshowitz,A., and Read,R., (1971), Cospectral graphs and digraphs, Bull. Lond. Math. Soc., 3, pp.321328.
11. [11] Johnson,C.R. and Newman,M., (1980), A note on cospectral graphs, J. Comb. Theory, Ser. B, 28, pp.96103.
12. [12] Mohammadian,A. and Tayfeh-Rezaie,B., (2011), Graphs with four distinct Laplacian eigenvalues, J. Algebraic Combin., 34, pp.671-682.
13. [13] Omidi,G.R., (2009), On graphs with largest Laplacian eignnvalues at most 4, Australas. J. Combin., 44, pp.163-170.
14. [14] Rowlinson,P., (2007), The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math., 1, pp.445-471.
15. [15] van Dam,E.R. and Haemers,W.H., (2003), Which graphs are determined by their spectrum?, Linear Algebra. Appl., 373, pp.241-272.
16. [16] van Dam,E.R. and Haemers,W.H., (2009), Developments on spectral characterizations of graphs, Discrete Math., 309, pp.576-586.
17. [17] Wang,J., Zhao,H., and Huang,Q., (2012), Spectral charactrization of multicone graphs, Czech. Math. J., 62, pp.117-126.
18. [18] Wang,J., Belardo,F., Huang,Q., and Borovi´canin,B., (2010), On the two largest Q-eigenvalues of graphs, Discrete Math., 310, pp.2858-2866.
19. [19] West,D.B., (2001), Introduction to Graph Theory, Upper Saddle River, Prentice hall.