Laplacian spectral characterization of some graphs obtained by product operation. (English) Zbl 1242.05170

Summary: A graph is said to be DLS, if there is no other non-isomorphic graph with the same Laplacian spectrum. Let \(G\) be a DLS graph. We show that \(G\times K_{r}\) is DLS if \(G\) is disconnected. If \(G\) is connected, it is proved that \(G\times K_{r}\) is DLS under certain conditions. Applying this result, we prove that \(G\times K_{r}\) is DLS if \(G\) is a tree on \(n(n\geq 5)\) vertices or a unicyclic graph on \(n(n\geq 6)\) vertices.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI


[1] Boulet, R., The centipede is determined by its Laplacian spectrum, C. R. acad. sci. Paris, ser. I, 346, 711-716, (2008) · Zbl 1154.05319
[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] Boulet, R., Spectral characterizations of Sun graphs and broken Sun graphs, Discrete math. theor. comput. sci., 11, 149-160, (2009) · Zbl 1250.05071
[4] Boulet, R.; Jouve, B., The lollipop graphs is determined by its spectrum, Electron. J. combin., 15, #R74, (2008) · Zbl 1163.05324
[5] Bu, C.; Zhou, J., Starlike trees whose maximum degree exceed 4 are determined by their \(Q\)-spectra, Linear algebra appl., 436, 143-151, (2012) · Zbl 1242.05160
[6] Cvetković, D.; Rowlinson, P.; Simić, S., An introduction to the theory of graph spectra, (2010), Cambridge University Press Cambridge · Zbl 1211.05002
[7] Cvetković, D.; Simić, S.; Stanić, Z., Spectral determination of graphs whose components are paths and cycles, Comput. math. appl., 59, 3849-3857, (2010) · Zbl 1198.05110
[8] Haemers, W.H.; Liu, X.; Zhang, Y., Spectral characterizations of lollipop graphs, Linear algebra appl., 428, 2415-2423, (2008) · Zbl 1226.05156
[9] Kirkland, S.J.; Molitierno, J.J.; Neumann, M.; Shader, B., On graphs with equal algebraic and vertex connectivity, Linear algebra appl., 341, 45-56, (2002) · Zbl 0991.05071
[10] 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
[11] 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
[12] 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
[13] Liu, X.; Zhang, Y.; Lu, P., One special double starlike graph is determined by its Laplacian spectrum, Appl. math. lett., 22, 435-438, (2009) · Zbl 1225.05173
[14] Ma, H.; Ren, H., On the spectral characterization of the union of complete multipartite graph and some isolated vertices, Discrete math., 310, 3648-3652, (2010) · Zbl 1200.05132
[15] Omidi, G.R.; Tajbakhsh, K., Starlike trees are determined by their Laplacian spectrum, Linear algebra appl., 422, 654-658, (2007) · Zbl 1114.05064
[16] Shen, X.; Hou, Y.; Zhang, Y., Graph \(Z_n\) and some graphs related to \(Z_n\) are determined by their spectrum, Linear algebra appl., 404, 58-68, (2005) · Zbl 1089.05050
[17] Simić, S.; Stanić, Z., On some forests determined by their Laplacian or signless Laplacian spectrum, Comput. math. appl., 58, 171-178, (2009) · Zbl 1189.05106
[18] Stanić, Z., On determination of caterpillars with four terminal vertices by their Laplacian spectrum, Linear algebra appl., 431, 2035-2048, (2009) · Zbl 1226.05165
[19] van Dam, E.R.; Haemers, W.H., Which graphs are determined by their spectra?, Linear algebra appl., 373, 241-272, (2003) · Zbl 1026.05079
[20] van Dam, E.R.; Haemers, W.H., Developments on spectral characterizations of graphs, Discrete math., 309, 576-586, (2009) · Zbl 1205.05156
[21] Wang, J.F.; Huang, Q.X.; Belardo, F.; Li Marzi, E.M., On the spectral characterizations of \(\infty\)-graphs, Discrete math., 310, 1845-1855, (2010) · Zbl 1231.05174
[22] Wang, J.F.; Simić, S.; Huang, Q.X.; Belardo, F.; Li Marzi, E.M., Laplacian spectral characterization of disjoint union of paths and cycles, Linear multilinear algebra, 59, 531-539, (2011) · Zbl 1223.05182
[23] Zhang, X.D., Two sharp upper bounds for the Laplacian eigenvalues, Linear algebra appl., 376, 207-213, (2004) · Zbl 1037.05032
[24] Zhang, Y.; Liu, X.; Yong, X., Which wheel graphs are determined by their Laplacian spectra?, Comput. math. appl., 58, 1887-1890, (2009) · Zbl 1189.05111
[25] 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.