The spectral determinations of the connected multicone graphs $ K_w\bigtriangledown mP_{17} $ and $ K_w\bigtriangledown mS $

Abdian, Ali Zeydi ; Mirafzal, S. Morteza

Czechoslovak Mathematical Journal, Tome 68 (2018) no. 4, pp. 1091-1104

Abstract (VO)

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.

Détail

DOI : 10.21136/CMJ.2018.0098-17

Classification : 05C50
Keywords: DS (determined by spectrum) graph; Schläfli graph; multicone graph; adjacency spectrum; Laplacian spectrum; Paley graph of order 17

Bibliographie

[1] Abdian, A. Z.: Graphs which are determined by their spectrum. Konuralp J. Math. 4 (2016), 34-41. | MR | JFM

[2] Abdian, A. Z.: Two classes of multicone graphs determined by their spectra. J. Math. Ext. 10 (2016), 111-121. | MR

[3] Abdian, A. Z.: Graphs cospectral with multicone graphs $ K_w\bigtriangledown L(P) $. TWMS. J. App. Eng. Math. 7 (2017), 181-187. | MR

[4] Abdian, A. Z.: The spectral determinations of the multicone graphs $K_w\bigtriangledown P$. Avaible at (2017). | arXiv | MR

[5] Abdian, A. Z., Mirafzal, S. M.: On new classes of multicone graphs determined by their spectrums. Alg. Struc. Appl. 2 (2015), 23-34. | MR

[6] Abdian, A. Z., Mirafzal, S. M.: 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 | MR | JFM

[7] Abdollahi, A., Janbaz, S., Oboudi, M. R.: Graphs cospectral with a friendship graph or its complement. Trans. Comb. 2 (2013), 37-52. | MR | JFM

[8] Bapat, R. B.: Graphs and Matrices. Universitext, Springer, London; Hindustan Book Agency, New Delhi (2014). | DOI | MR | JFM

[9] Biggs, N.: Algebraic Graph Theory. Cambridge Mathematical Library, Cambridge University Press, Cambridge (1994). | DOI | MR | JFM

[10] Boulet, R., Jouve, B.: The lollipop graph is determined by its spectrum. Electron. J. Comb. 15 (2008), Researh Paper 74, 43 pages. | MR | JFM

[11] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext, Springer, New York (2012). | DOI | MR | JFM

[12] Cioabă, S. M., Haemers, W. H., Vermette, J. R., Wong, W.: The graphs with all but two eigenvalues equal to $\pm1$. J. Algebr. Comb. 41 (2015), 887-897. | DOI | MR | JFM

[13] Cvetković, D., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75, Cambridge University Press, Cambridge (2010). | DOI | MR | JFM

[14] Das, K. C.: Proof of conjectures on adjacency eigenvalues of graphs. Discrete Math. 313 (2013), 19-25. | DOI | MR | JFM

[15] Doob, M., Haemers, W. H.: The complement of the path is determined by its spectrum. Linear Algebra Appl. 356 (2002), 57-65. | DOI | MR | JFM

[16] Günthard, H. H., Primas, H.: Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen. Helv. Chim. Acta. German 39 (1956), 1645-1653. | DOI

[17] Haemers, W. H., Liu, X., Zhang, Y.: Spectral characterizations of lollipop graphs. Linear Algebra Appl. 428 (2008), 2415-2423. | DOI | MR | JFM

[18] Knauer, U.: Algebraic Graph Theory. Morphisms, Monoids and Matrices. De Gruyter Studies in Mathematics 41, Walter de Gruyter, Berlin (2011). | DOI | MR | JFM

[19] Liu, Y., Sun, Y. Q.: On the second Laplacian spectral moment of a graph. Czech. Math. J. 60 (2010), 401-410. | DOI | MR | JFM

[20] Merris, R.: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197/198 (1994), 143-176. | DOI | MR | JFM

[21] Mirafzal, S. M., Abdian, A. Z.: Spectral characterization of new classes of multicone graphs. Stud. Univ. Babeş-Bolyai Math. 62 (2017), 275-286. | DOI | MR | JFM

[22] Peisert, W.: All self-complementary symmetric graphs. J. Algebra 240 (2001), 209-229. | DOI | MR | JFM

[23] Rowlinson, P.: The main eigenvalues of a graph: A survey. Appl. Anal. Discrete Math. 1 (2007), 445-471. | DOI | MR | JFM

[24] Dam, E. R. van: Nonregular graphs with three eigenvalues. J. Comb. Theory, Ser. B 73 (1998), 101-118. | DOI | MR | JFM

[25] Dam, E. R. van, Haemers, W. H.: Which graphs are determined by their spectrum?. Linear Algebra Appl. 373 (2003), 241-272. | DOI | MR | JFM

[26] Dam, E. R. van, Haemers, W. H.: Developments on spectral characterizations of graphs. Discrete Math. 309 (2009), 576-586. | DOI | MR | JFM

[27] Wang, J., Belardo, F., Huang, Q., Borovićanin, B.: On the two largest $Q$-eigenvalues of graphs. Discrete Math. 310 (2010), 2858-2866. | DOI | MR | JFM

[28] Wang, W., Xu, C.: A sufficient condition for a family of graphs being determined by their generalized spectra. Eur. J. Comb. 27 (2006), 826-840. | DOI | MR | JFM

[29] Wang, J., Zhao, H., Huang, Q.: Spectral characterization of multicone graphs. Czech. Math. J. 62 (2012), 117-126. | DOI | MR | JFM

[30] West, D. B.: Introduction to Graph Theory. Prentice-Hall of India, New Delhi (2005). | MR | JFM