Czechoslovak Mathematical Journal, Vol. 68, No. 4, pp. 1091-1104, 2018
The spectral determinations of the connected multicone graphs $ K_w\bigtriangledown mP_{17} $ and $ K_w\bigtriangledown mS $
Ali Zeydi Abdian, S. Morteza Mirafzal
Received March 8, 2017. Published online April 27, 2018.
Abstract: Finding and discovering any class of graphs which are determined by their spectra is always an important and interesting problem in the spectral graph theory. The main aim of this study is to characterize two classes of multicone graphs which are determined by both their adjacency and Laplacian spectra. A multicone graph is defined to be the join of a clique and a regular graph. Let $ K_w $ denote a complete graph on $ w $ vertices, and let $ m $ be a positive integer number. In A. Z. Abdian (2016) it has been shown that multicone graphs $ K_w\bigtriangledown P_{17}$ and $ K_w\bigtriangledown S$ are determined by both their adjacency and Laplacian spectra, where $ P_{17} $ and $ S$ denote the Paley graph of order 17 and the Schläfli graph, respectively. In this paper, we generalize these results and we prove that multicone graphs $ K_w\bigtriangledown mP_{17}$ and $ K_w\bigtriangledown mS$ are determined by their adjacency spectra as well as their Laplacian spectra.
Keywords: DS (determined by spectrum) graph; Schläfli graph; multicone graph; adjacency spectrum; Laplacian spectrum; Paley graph of order 17
References: [1] A. Z. Abdian: Graphs which are determined by their spectrum. Konuralp J. Math. 4 (2016), 34-41. MR 3571504 | Zbl 1355.05152
[2] A. Z. Abdian: Two classes of multicone graphs determined by their spectra. J. Math. Ext. 10 (2016), 111-121. MR 3621464
[3] A. Z. Abdian: Graphs cospectral with multicone graphs $ K_w\bigtriangledown L(P) $. TWMS. J. App. Eng. Math. 7 (2017), 181-187. MR 3741897
[4] A. Z. Abdian: The spectral determinations of the multicone graphs $K_w\bigtriangledown P$. Avaible at https://arxiv.org/abs/1706.02661 (2017).
[5] A. Z. Abdian, S. M. Mirafzal: On new classes of multicone graphs determined by their spectrums. Alg. Struc. Appl. 2 (2015), 23-34.
[6] A. Z. Abdian, S. M. Mirafzal: The spectral characterizations of the connected multicone graphs $K_w\bigtriangledown LHS$ and $K_w\bigtriangledown LGQ(3,9) $. Discrete Math. Algorithms Appl. 10 (2018), Article ID 1850019. DOI 10.1142/S1793830918500192 | MR 3786377 | Zbl 1383.05190
[7] A. Abdollahi, S. Janbaz, M. R. Oboudi: Graphs cospectral with a friendship graph or its complement. Trans. Comb. 2 (2013), 37-52. MR 3150451 | Zbl 1302.05083
[8] R. B. Bapat: Graphs and Matrices. Universitext, Springer, London; Hindustan Book Agency, New Delhi, 2014. DOI 10.1007/978-1-4471-6569-9 | MR 3289036 | Zbl 1301.05001
[9] N. Biggs: Algebraic Graph Theory. Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1994. DOI 10.1017/CBO9780511608704 | MR 1271140 | Zbl 0797.05032
[10] R. Boulet, B. Jouve: The lollipop graph is determined by its spectrum. Electron. J. Comb. 15 (2008), Researh Paper 74, 43 pages. MR 2411451 | Zbl 1163.05324
[11] A. E. Brouwer, W. H. Haemers: Spectra of Graphs. Universitext, Springer, New York, 2012. DOI 10.1007/978-1-4614-1939-6 | MR 2882891 | Zbl 1231.05001
[12] S. M. Cioabă, W. H. Haemers, J. R. Vermette, W. Wong: The graphs with all but two eigenvalues equal to $\pm1$. J. Algebr. Comb. 41 (2015), 887-897. DOI 10.1007/s10801-014-0557-y | MR 3328184 | Zbl 1317.05111
[13] D. Cvetković, P. Rowlinson, S. Simić: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75, Cambridge University Press, Cambridge, 2010. DOI 10.1017/CBO9780511801518 | MR 2571608 | Zbl 1211.05002
[14] K. C. Das: Proof of conjectures on adjacency eigenvalues of graphs. Discrete Math. 313 (2013), 19-25. DOI 10.1016/j.disc.2012.09.017 | MR 3016969 | Zbl 1254.05099
[15] M. Doob, W. H. Haemers: The complement of the path is determined by its spectrum. Linear Algebra Appl. 356 (2002), 57-65. DOI 10.1016/S0024-3795(02)00323-3 | MR 1944676 | Zbl 1015.05047
[16] H. H. Günthard, H. Primas: Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen. Helv. Chim. Acta. 39 (1956), 1645-1653. (In German.) DOI 10.1002/hlca.19560390623
[17] W. H. Haemers, X. Liu, Y. Zhang: Spectral characterizations of lollipop graphs. Linear Algebra Appl. 428 (2008), 2415-2423. DOI 10.1016/j.laa.2007.10.018 | MR 2416560 | Zbl 1226.05156
[18] U. Knauer: Algebraic Graph Theory. Morphisms, Monoids and Matrices. De Gruyter Studies in Mathematics 41, Walter de Gruyter, Berlin, 2011. DOI 10.1515/9783110255096 | MR 2848562 | Zbl 1338.05001
[19] Y. Liu, Y. Q. Sun: On the second Laplacian spectral moment of a graph. Czech. Math. J. 60 (2010), 401-410. DOI 10.1007/s10587-010-0043-1 | MR 2657957 | Zbl 1224.05312
[20] R. Merris: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197/198 (1994), 143-176. DOI 10.1016/0024-3795(94)90486-3 | MR 1275613 | Zbl 0802.05053
[21] S. M. Mirafzal, A. Z. Abdian: Spectral characterization of new classes of multicone graphs. Stud. Univ. Babeş-Bolyai Math. 62 (2017), 275-286. DOI 10.24193/subbmath.2017.3.01 | MR 3714100 | Zbl 06847482
[22] W. Peisert: All self-complementary symmetric graphs. J. Algebra 240 (2001), 209-229. DOI 10.1006/jabr.2000.8714 | MR 1830551 | Zbl 1021.05051
[23] P. Rowlinson: The main eigenvalues of a graph: A survey. Appl. Anal. Discrete Math. 1 (2007), 445-471. DOI 10.2298/AADM0702445R | MR 2355287 | Zbl 1199.05241
[24] E. R. van Dam: Nonregular graphs with three eigenvalues. J. Comb. Theory, Ser. B 73 (1998), 101-118. DOI 10.1006/jctb.1998.1815 | MR 1631983 | Zbl 0917.05044
[25] E. R. van Dam, 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 | MR 2022290 | Zbl 1026.05079
[26] E. R. van Dam, W. H. Haemers: Developments on spectral characterizations of graphs. Discrete Math. 309 (2009), 576-586. DOI 10.1016/j.disc.2008.08.019 | MR 2499010 | Zbl 1205.05156
[27] J. Wang, F. Belardo, Q. Huang, B. Borovićanin: On the two largest $Q$-eigenvalues of graphs. Discrete Math. 310 (2010), 2858-2866. DOI 10.1016/j.disc.2010.06.030 | MR 2677645 | Zbl 1208.05079
[28] W. Wang, C. Xu: A sufficient condition for a family of graphs being determined by their generalized spectra. Eur. J. Comb. 27 (2006), 826-840. DOI 10.1016/j.ejc.2005.05.004 | MR 2226420 | Zbl 1092.05050
[29] J. Wang, H. Zhao, Q. Huang: Spectral characterization of multicone graphs. Czech. Math. J. 62 (2012), 117-126. DOI 10.1007/s10587-012-0021-x | MR 2899739 | Zbl 1249.05256
[30] D. B. West: Introduction to Graph Theory. Prentice-Hall of India, New Delhi, 2005. MR 1367739 | Zbl 1121.05304
Affiliations: Ali Zeydi Abdian, Department of the Mathematical Science, Lorestan University, College of Science, Lorestan, Khoramabad, Iran, e-mail: azeydiabdi@gmail.com, abdian.al@fs.lu.ac.ir; S. Morteza Mirafzal, Department of Mathematics, Lorestan University, Faculty of Science, Lorestan, Khoramabad, Iran, e-mail: smortezamirafzal@yahoo.com, mirafzal.m@lu.ac.ir
