The Spectral Determinations of the Multicone Graphs $ K_w\bigtriangledown P_{17}\bigtriangledown P_{17} $ and $ K_w\bigtriangledown S\bigtriangledown S$

Year 2019, Volume: 7 Issue: 1, 192 - 198, 15.04.2019

Maryam Rahmani Moghaddam Kewen Zhao , Sara Pouyandeh Ali Zeydi Abdian

Abstract

Characterizing classes of graphs which are determined by their spectra is often a hard and challenging problem. So, finding and introducing any class of these graphs can be an interesting and important problem. This paper aims to characterize new classes of multicone graphs which are determined by both their adjacency spectra and their Laplacian spectra. A multicone graph is obtained from the join of a clique and a regular graph. Let $ K_w $ be a complete graph on $ w $ vertices. It is proved that multicone graphs $ K_w\bigtriangledown P_{17}\bigtriangledown P_{17}$ and $ K_w\bigtriangledown S\bigtriangledown S$ are determined by both their adjacency spectra and their Laplacian spectra, where $ P_{17} $ and $S$ denote Paley graph of order 17 and Schlafli graph, respectively.

Keywords

Adjacency spectrum , Laplacian spectrum , Multicone graph , Paley graph of order 17 , DS graph , Schlafli graph

References

• [1] A.Z. Abdian and S.M. Mirafzal, On new classes of multicone graphs determined by their spectrums, Alg. Struc. Appl, 2 (2015), 23-34.
• [2] A.Z. Abdian, Graphs which are determined by their spectrum, Konuralp. J. Math, 4 (2016), 34–41.
• [3] A.Z. Abdian, Two classes of multicone graphs determined by their spectra, J. Math. Ext. 10 (2016), 111–121.
• [4] A.Z. Abdian, Graphs cospectral with multicone graphs Kw5L(P), TWMS. J. App. and Eng. Math., 7 (2017), 181–187.
• [5] A.Z. Abdian, The spectral determinations of the multicone graphs Kw5P, arXiv:1706.02661.
• [6] A.Z. Abdian and S. M. Mirafzal, The spectral characterizations of the connected multicone graphs Kw5LHS and Kw5LGQ(3;9), Discrete Math. Algorithm and Appl (DMAA), 10 (2018), 1850019.
• [7] A.Z. Abdian and S. M. Mirafzal, The spectral determinations of the connected multicone graphs Kw5mP17 and Kw5mS, Czech. Math. J., (2018), 1–14, DOI 10.21136/CMJ.2018.0098-17.
• [8] A.Z. Abdian, The spectral determinations of the multicone graphs Kw5mCn, arXiv preprint arXiv:1703.08728.
• [9] A.Z. Abdian and et al., On the spectral determinations of the connected multicone graphs Kr 5 sKt , AKCE Int. J. Graphs and Combin., 10.1016/j.akcej.2018.11.002.
• [10] A.Z. Abdian, A. Behmaram and G.H. Fath-Tabar, Graphs determined by signless Laplacian spectra, AKCE Int. J. Graphs and Combin., https://doi.org/10.1016/j.akcej.2018.06.00.
• [11] A.Z. Abdian, G.H. Fath-Tabar, and M.R. Moghaddam, The spectral determination of the multicone graphs Kw 5C with respect to their signless Laplacian spectra, Journal of Algebraic Systems, (to appear).
• [12] R. B. Bapat, Graphs and Matrices, Springer (2010).
• [13] N. L. Biggs, Algebraic Graph Theory, Cambridge Univ. Press (1974).
• [14] R. Boulet and B. Jouve, The lollipop graph is determined by its spectrum, Electron. J. Combin., 15 (2008), R74.
• [15] A. Brandstadt, V. B. Le, J. P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, (1999).
• [16] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext. Springer, (2012).
• [17] S. M. Cioaba, W. H. Haemers, J. R. Vermette and W. Wong, The graphs with all but two eigenvalues equal to 1, J. Algebraic Combin., 41 (2013), 887–897.
• [18] D. Cvetkovic, P. Rowlinson and S. Simi´c, An Introduction to the Theory of Graph Spectra, London Mathematical Society Student Texts 75, Cambridge Univ. Press (2010).
• [19] M. Doob and W. H. Haemers, The complement of the path is determined by its spectrum, Linear Algebra Appl., 356 (2002), 57–65.
• [20] H. H. G¨unthard and H. Primas, Zusammenhang von Graph Theory und Mo-Theorie von Molekeln mit Systemen konjugierter Bindungen, Helv. Chim. Acta, 39 (1925), 1645–1653.
• [21] W. H. Haemers, X. G. Liu and Y. P. Zhang, Spectral characterizations of lollipop graphs, Linear Algebra Appl., 428 (2008), 2415–2423.
• [22] U. Knauer, Algebraic Graph Theory, Morphism, Monoids and Matrices, de Gruyters Studies in Mathematics, de Gruyters, 41 (2011).
• [23] Y. Hong, J. Shu and K. Fang, A sharp upper bound of the spectral radius of graphs, J. Combin., Theory Ser. B, 81 (2001) 177–183.
• [24] M.-H. Liu, Some graphs determined by their (signless) Laplacian spectra, Czech. Math. J., 62 (2012), 1117–1134.
• [25] Y. Liu and Y. Q. Sun, On the second Laplacian spectral moment of a graph, Czech. Math. J., 60 (2010), 401–410.
• [26] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197 (1994), 143–176.
• [27] S.M. Mirafzal and A.Z. Abdian, Spectral characterization of new classes of multicone graphs, Studia. Univ. Babes¸-Bolyai Mathematica, 62 (2017), 275–286.
• [28] S.M. Mirafzal and A.Z. Abdian, The spectral determinations of some classes of multicone graphs, J. Discrete Math. Sci. Cryptogr. 21 (2018), 179–189.
• [29] W. Peisert, All self-complementary symmetric graphs, J. Algebra, 240 (2001), 209–229.
• [30] P. Rowlinson, The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math., 1 (2007), 445–471.
• [31] R. Sharafdini and A.Z. Abdian, Signless Laplacian determinations of some graphs with independent edges, Carpathian Math. Publ., 10 (2018), 185–191.
• [32] E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra. Appl., 373 (2003), 241–272.
• [33] E. R. van Dam and W. H. Haemers, Developments on spectral characterizations of graphs, Discrete Math., 309 (2009), 576–586.
• [34] J. Wang and Q. Huang, Spectral characterization of generalized cocktail-party graphs, J. Math. Res. Appl., 32 (2012), 666–672.
• [35] J. Wang, F. Belardo, Q. Huang, and B. Borovi´canin, On the two largest Q-eigenvalues of graphs, Discrete Math. 310 (2010), 2858–2866.
• [36] W. Wang and C. X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra. European J. Combin. 27 (2006), 826-840.
• [37] J. Wang, H. Zhao, and Q. Huang, Spectral characterization of multicone graphs, Czech. Math. J. 62 (2012), 117–126.
• [38] D. B. West, Introduction to Graph Theory (2nd ed.), Prentice Hall (2001).
• [39] Y. Zhang, X. Liu, and X. Yong, Which wheel graphs are determined by their Laplacian spectra? Comput. Math. Appl. 58 (2009) 1887–1890.