Some graphs determined by their (signless) Laplacian spectra. (English) Zbl 1286.05094
Summary: A graph \(G\) is L-DS (respectively, Q-DS) if there is no other non-isomorphic graph with the same (respectively, signless) Laplacian spectrum as \(G\). Let \(G_1 \vee G_2\) be the join graph of graphs \(G_1\) and \(G_2\), and \(U_{r,n-r}\) the graph obtained by attaching \(n-r\) pendent vertices to a vertex of \(C_r\) (the cycle of order \(r\)). In this paper, we prove that if \(G\) is L-DS and the algebraic connectivity of \(G\) is less than three, then \(K_t \vee G\) is L-DS under certain condition, which extends the main result of J. Zhou and C. Bu [Discrete Math. 312, No. 10, 1591–1595 (2012; Zbl 1242.05170)]. Also, \(U_{r,n-r}\) is proved to be Q-DS for \(r\geqslant 3\).
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 15B36 | Matrices of integers |
Citations:
Zbl 1242.05170References:
| [1] | de Abreu, N. M.M., Old and new results on algebraic connectivity of graphs, Linear Algebra Appl., 423, 53-73 (2007) · Zbl 1115.05056 |
| [2] | Boulet, R., Disjoint unions of complete graphs characterized by their Laplacian spectrum, Electron. J. Linear Algebra, 18, 773-783 (2009) · Zbl 1189.05099 |
| [3] | Cvetković, D.; Rowlinson, P.; Simić, S. K., Signless Laplacians of finite graphs, Linear Algebra Appl., 423, 155-171 (2007) · Zbl 1113.05061 |
| [4] | Cvetković, D.; Rowlinson, P.; Simić, S. K., Eigenvalue bounds for the signless Laplacian, Publ. Inst. Math. (Beograd), 81, 95, 11-27 (2007) · Zbl 1164.05038 |
| [5] | van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079 |
| [6] | van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586 (2009) · Zbl 1205.05156 |
| [7] | Das, K. C., On conjectures involving second largest signless Laplacian eigenvalue of graphs, Linear Algebra Appl., 432, 3018-3029 (2010) · Zbl 1195.05040 |
| [8] | Fiedler, M., Algebraic connectivity of graphs, Czechoslovak Math. J., 23, 298-305 (1973) · Zbl 0265.05119 |
| [9] | Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 227-228, 593-616 (1995) · Zbl 0831.05044 |
| [10] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press London · Zbl 0576.15001 |
| [11] | Kirkland, S., A bound on the algebraic connectivity of a graph in terms of the number of cutpoints, Linear Multilinear Algebra, 47, 93-103 (2000) · Zbl 0947.05052 |
| [12] | Lin, Y.; Shu, J.; Meng, Y., Laplacian spectrum characterization of extensions of vertices of wheel graphs and multi-fan graphs, Comput. Math. Appl., 60, 2003-2008 (2010) · Zbl 1205.05147 |
| [13] | Liu, M.; Liu, B., Some results on the Laplacian spectrum, Comput. Appl. Math., 59, 3612-3616 (2010) · Zbl 1197.05091 |
| [14] | Liu, M.; Tan, X.; Liu, B., The (signless) Laplacian spectral radius of unicyclic and bicyclic graphs with \(n\) vertices and \(k\) pendant vertices, Czechoslovak Math. J., 60, 849-867 (2010) · Zbl 1224.05311 |
| [15] | Liu, X.; Wang, S., Laplacian spectral characterization of some graph products, Linear Algebra Appl., 437, 1749-1759 (2012) · Zbl 1247.05201 |
| [16] | Liu, X.; Wang, S.; Zhang, Y.; Yong, X., On the spectral characterization of some unicyclic graphs, Discrete Math., 311, 2317-2336 (2011) · Zbl 1242.05165 |
| [17] | Liu, X.; Zhang, Y.; Gui, X., The multi-fan graphs are determined by their Laplacian spectra, Discrete Math., 308, 4267-4271 (2008) · Zbl 1225.05172 |
| [18] | Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197-198, 143-176 (1994) · Zbl 0802.05053 |
| [19] | Omidi, G. R., On a signless Laplacian spectral characterization of \(T\)-shape trees, Linear Algebra Appl., 431, 1607-1615 (2009) · Zbl 1169.05351 |
| [20] | Omidi, G. R.; Tajbakhsh, K., Starlike trees are determined by their Laplacian spectrum, Linear Algebra Appl., 422, 654-658 (2007) · Zbl 1114.05064 |
| [21] | Zhang, X.; Zhang, H., Some graphs determined by their spectra, Linear Algebra Appl., 431, 1443-1454 (2009) · Zbl 1169.05354 |
| [22] | Zhang, Y.; Liu, X.; Yong, X., Which wheel graphs are determined by their Laplacian spectra, Comput. Appl. Math., 58, 1887-1890 (2009) · Zbl 1189.05111 |
| [23] | Zhang, Y.; Liu, X.; Zhang, B.; Yong, X., The lollipop graph is determined by its Q-spectrum, Discrete Math., 309, 3364-3369 (2009) · Zbl 1182.05084 |
| [24] | Zhou, J.; Bu, C., Laplacian spectral characterization of some graphs obtained by product operation, Discrete Math., 312, 1591-1595 (2012) · Zbl 1242.05170 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
