On the spectral characterization of kite graphs

Year 2016, , 81 - 90, 15.05.2016

Sezer Sorgun , Hatice Topcu

https://doi.org/10.13069/jacodesmath.01767

Cited By: 2

Abstract

The Kite graph, denoted by $Kite_{p,q}$ is obtained by appending a complete graph $K_{p}$ to a pendant vertex of a path $P_{q}$. In this paper, firstly we show that no two non-isomorphic kite graphs are cospectral w.r.t the adjacency matrix. Let $G$ be a graph which is cospectral with $Kite_{p,q}$ and let $w(G)$ be the clique number of $G$. Then, it is shown that $w(G)\geq p-2q+1$. Also, we prove that $Kite_{p,2}$ graphs are determined by their adjacency spectrum.

Keywords

Kite graph, Cospectral graphs, Clique number, Determined by adjacency spectrum

References

• [1] R. Boulet, B. Jouve, The lollipop graph is determined by its spectrum, Electron. J. Combin. 15(1) (2008) Research Paper 74, 43 pp.
• [2] M. Camara, W. H. Haemers, Spectral characterizations of almost complete graphs, Discrete Appl. Math. 176 (2014) 19–23.
• [3] M. D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge University Press, 2010.
• [4] E.R. van Dam, W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003) 241–272.
• [5] E.R. van Dam, W. H. Haemers, Developments on spectral characterizations of graphs, Discrete Math. 309(3) (2009) 576–586.
• [6] M. Doob, W. H. Haemers, The complement of the path is determined by its spectrum, Linear Algebra Appl. 356(1-3) (2002) 57–65.
• [7] N. Ghareghani, G. R. Omidi, B. Tayfeh-Rezaie, Spectral characterization of graphs with index at most $\sqrt{2+\sqrt{5}}$, Linear Algebra Appl. 420(2-3) (2007) 483–486.
• [8] W. H. Haemers, X. Liu, Y. Zhang, Spectral characterizations of lollipop graphs, Linear Algebra Appl. 428(11-12) (2008) 2415–2423.
• [9] F. Liu, Q. Huang, J. Wang, Q. Liu, The spectral characterization of $\infty$-graphs, Linear Algebra Appl. 437(7) (2012) 1482–1502.
• [10] M. Liu, H. Shan, K. Ch. Das, Some graphs determined by their (signless) Laplacian spectra, Linear Algebra Appl. 449 (2014) 154–165.
• [11] X. Liu, Y. Zhang, X. Gui, The multi-fan graphs are determined by their Laplacian spectra, Discrete Math. 308(18) (2008) 4267–4271.
• [12] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11(2) (2002) 179–189.
• [13] G. R. Omidi, On a signless Laplacian spectral characterization of T-shape trees, Linear Algebra Appl. 431(9) (2009) 1607–1615.
• [14] D. Stevanovic, P. Hansen, The minimum spectral radius of graphs with a given clique number, Electron. J. Linear Algebra. 17 (2008) 110–117.
• [15] X. Zhang, H. Zhang, Some graphs determined by their spectra, Linear Algebra Appl. 431(9) (2009) 1443–1454.