The main goal of this study is to characterize new classes of multicone graphs which are determined by their spectra. One of important part of algebraic graph theory is devoted to spectral graph theory. Determining whether a graph is determined by its spectra or not is often an important and challenging problem. In [1] it have been shown that the join of a Cocktail-Party graph with an arbitrary complete graph is determined by both its adjacency spectra and its Laplacian spectra. In this work, we aim to generalize these facts. A multicone graph is defined to be the join of a clique and a regular graph. Let w, m and n be natural numbers. In this paper, it is proved that any connected graph cospectral to a multicone graph Kw ▽ mCP(n) is determined by its adjacency spectra as well as its Laplacian spectra, where $ CP(n) = {K_{\underbrace {2, \, .\, .\, ., \, \, 2}_{n\, times}}}$ is a Cocktail-Party graph. Moreover, we prove that any graph cospectral to one of these multicone graphs must be perfect. Finally, we pose two conjectures for further research.
Citation: Sara Pouyandeh, Amirhossein Morovati Moez, Ali Zeydi Abdian. The spectral determinations of connected multicone graphs Kw ▽ mCP(n)[J]. AIMS Mathematics, 2019, 4(5): 1348-1356. doi: 10.3934/math.2019.5.1348
The main goal of this study is to characterize new classes of multicone graphs which are determined by their spectra. One of important part of algebraic graph theory is devoted to spectral graph theory. Determining whether a graph is determined by its spectra or not is often an important and challenging problem. In [1] it have been shown that the join of a Cocktail-Party graph with an arbitrary complete graph is determined by both its adjacency spectra and its Laplacian spectra. In this work, we aim to generalize these facts. A multicone graph is defined to be the join of a clique and a regular graph. Let w, m and n be natural numbers. In this paper, it is proved that any connected graph cospectral to a multicone graph Kw ▽ mCP(n) is determined by its adjacency spectra as well as its Laplacian spectra, where $ CP(n) = {K_{\underbrace {2, \, .\, .\, ., \, \, 2}_{n\, times}}}$ is a Cocktail-Party graph. Moreover, we prove that any graph cospectral to one of these multicone graphs must be perfect. Finally, we pose two conjectures for further research.
| [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 Kw ▽ L(P), TWMS. J. App. Eng. Math., 7 (2017), 181-187. |
| [5] | A. Z. Abdian, The spectral determinations of the multicone graphs Kw ▽ P, arXiv: 1706.02661. |
| [6] | A. Z. Abdian and S. M. Mirafzal, The spectral characterizations of the connected multicone graphs Kw ▽ LHS and Kw ▽ LGQ(3, 9), Discrete Math. Algorithm. Appl., 10 (2018), 1850019. |
| [7] | A. Z. Abdian and S. M. Mirafzal, The spectral determinations of the connected multicone graphs Kw ▽ mP17 and Kw ▽ mS, Czech. Math. J., 68 (2018), 1091-1104. |
| [8] | A. Z. Abdian, The spectral determinations of the multicone graphs Kw ▽ mCn, arXiv preprint arXiv: 1703.08728. |
| [9] | A. Z. Abdian, L. W. Beineke, M. R. Oboudi, et al., On the spectral determinations of the connected multicone graphs Kr ▽ sKt, AKCE Int. J. Graphs Combin., arXiv preprint arXiv: 1806.02625. |
| [10] | A. Z. Abdian, A. Behmaram and G. H. Fath-Tabar, Graphs determined by signless Laplacian spectra, AKCE Int. J. Graphs 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 ▽ C with respect to their signless Laplacian spectra, J. Alg. Systems, (to appear). |
| [12] | A. Z. Abdian, S. Pouyandeh and B. Askari, Which multicone graphs Kn▽ Km are determined by their signless Laplacian spectrum?(the proof of a conjecture), J. Discrete Math., Sci. and Cryp., 22 (2019), 91-99. |
| [13] | A. Z. Abdian and A. M. Moez, The spectral determination of the join of two friendship graphs, Honam Math. J., 41 (2019), 67-87. |
| [14] | A. Z. Abdian and A. R. Ashrafi, No two Jellyfish graphs are L-cospectral and Q-cospectral, arXiv preprint arXiv: 1908.07909. |
| [15] | M. R. Moghaddam, K. Zhao, S. Pouyandeh, et al., The spectral determination of the multicone graphs Kw ▽ P17 ▽ P17 and Kw ▽ S ▽ S, Konuralp. J. Math., 7 (2019), 192-198. |
| [16] | A. Z. Abdian, A. R. Ashrafi, L. W. Beineke, et al., Laplacian spectral determination of pathfriendship graphs, arXiv preprint arXiv: 1903.11121. |
| [17] | A. Brandstädt, V. B. Le and J. P. Spinrad, Graph Classes:A Survey, SIAM, 1999. |
| [18] | R. B. Bapat, Graphs and Matrices, London: Springer, 2010. |
| [19] | N. Biggs, Algebraic Graph Theory, Cambridge:Cambridge University press, 1993. |
| [20] | X. M. Cheng, G. R. W. Greaves, J. H. Koolen, Graphs with three eigenvalues and second largest eigenvalue at most 1, J. Comb. Theory B, 129 (2018), 55-78. |
| [21] | S. M. Cioabä, W. H. Haemers, J. R. Vermette, et al., The graphs with all but two eigenvalues equal to ±1, J. Algebr. Combin., 41 (2013), 887-897. |
| [22] | D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra, Cambridge:Cambridge University Press, 2010. |
| [23] | U. Knauer, Algebraic Graph Theory: Morphism, Monoids and Matrices, Berlin: Walter de Gruyter, 2011. |
| [24] | S. M. Mirafzal and A. Z. Abdian, Spectral characterization of new classes of multicone graphs, Stud. Univ. Babes-Bolyai Math., 62 (2017), 275-286. |
| [25] | S. M. Mirafzal and A. Z. Abdian, The spectral determinations of some classes of multicone graphs, J. Discrete Math. Sci. Crypt., 21 (2018), 179-189. |
| [26] | R. Sharafdini and A. Z. Abdian, signless Laplacian determination of some graph with independent edges, Carpathian Math. Publ., 10 (2018), 185-196. |
| [27] | P. Rowlinson, The main eigenvalues of a graph:A survey, Appl. Anal. Discrete Math., 1 (2007), 445-471. |
| [28] | D. Stevanović, I. Gutman and M. U. Rehman, On spectral radius and energy of complete multipartite graphs, Ars Math. Contemp., 9 (2014), 109-113. |
| [29] | E. R. Van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra. Appl., 373 (2003), 241-272. |
| [30] | E. R. Van Dam and W. H. Haemers, Developments on spectral characterizations of graphs, Discrete Math., 309 (2009), 576-586. |
| [31] | J. Wang, H. Zhao and Q. Huang, Spectral charactrization of multicone graphs, Czech. Math. J., 62 (2012), 117-126. |
| [32] | J. Wang, F. Belardo, Q. Huang, et al., On the two largest Q-eigenvalues of graphs, Discrete Math., 310 (2010), 2858-2866. |
| [33] | J. Wang and Q. Huang, Spectral characterization of generalized cocktail-party graphs, J. Math. Res. Appl., 32 (2012), 666-672. |
| [34] | D. B. West, Introduction to Graph Theory, Upper Saddle River:Prentice Hall, 1996. |
Sara Pouyandeh, Amirhossein Morovati Moez, Ali Zeydi Abdian. The spectral determinations of connected multicone graphs Kw ▽ mCP(n)[J]. AIMS Mathematics, 2019, 4(5): 1348-1356. doi: 10.3934/math.2019.5.1348
DownLoad: