×

The spectra and the signless Laplacian spectra of graphs with pockets. (English) Zbl 1426.05090

Summary: Let \(G[F,V_k,H_v]\) be the graph with \(k\) pockets, where \(F\) is a simple graph of order \(n\geq 1, V_k = \{v_1, \ldots, v_k \}\) is a subset of the vertex set of \(F\) and \(H_v\) is a simple graph of order \(m\geq 2, v\) is a specified vertex of \(H_v\). Also let \(G[F,E_k,H_{uv}]\) be the graph with \(k\) edge-pockets, where \(F\) is a simple graph of order \(n\geq 2, E_k = \{e_1, \ldots, e_k \}\) is a subset of the edge set of \(F\) and \(H_{uv}\) is a simple graph of order \(m\geq 3, uv\) is a specified edge of \(H_{uv}\) such that \(H_{u v} - u\) is isomorphic to \(H_{u v} - v\). In this paper, we obtain some results describing the signless Laplacian spectra of \(G[F,V_k,H_v]\) and \(G[F,E_k,H_{uv}]\) in terms of the signless Laplacian spectra of \(F,H_v\) and \(F,H_{uv}\), respectively. In addition, we also give some results describing the adjacency spectrum of \(G[F,V_k,H_v]\) in terms of the adjacency spectra of \(F, H_v\). Finally, as many applications of these results, we construct infinitely many pairs of signless Laplacian (resp. adjacency) cospectral graphs.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ackelsberg, E.; Brehm, Z.; Chan, A.; Mundinger, J.; Tamon, C., Laplacian state transfer in coronas, Linear Algebra Appl., 506, 154-167 (2016) · Zbl 1346.05158
[2] Ackelsberg, E.; Brehm, Z.; Chan, A.; Mundinger, J.; Tamon, C., Quantum state transfer in coronas, Electron. J. Comb., 24, 2, #P2.24 (2017) · Zbl 1364.05044
[3] Aouchiche, M.; Hansen, P., A survey of automated conjectures in spectral graph theory, Linear Algebra Appl., 432, 2293-2322 (2010) · Zbl 1218.05087
[4] Barik, S., On the Laplacian spectra of graphs with pockets, Linear Multilinear Algebra, 56, 481-490 (2008) · Zbl 1155.05042
[5] Barik, S.; Pati, S.; Sarma, B. K., The spectrum of the corona of two graphs, SIAM. J. Discrete Math., 24, 47-56 (2007) · Zbl 1138.05046
[6] Barik, S.; Sahoo, G., On the Laplacian spectra of some variants of corona, Linear Algebra Appl., 512, 32-47 (2017) · Zbl 1348.05120
[7] Brankov, V.; Hansen, P.; Stevanovic, D., Automated upper bounds on the largest Laplacian eigenvalue, Linear Algebra Appl., 414, 407-424 (2006) · Zbl 1086.05049
[8] Chen, H. Y.; Liao, L. W., The normalized Laplacian spectra of the corona and edge corona of two graphs, Linear Multilinear Algebra, 65, 582-592 (2017) · Zbl 1356.05081
[9] Coutinho, G., Quantum state transfer in graphs (2014), University of Waterloo, PhD thesis
[10] Coutinho, C.; Godsil, C., Perfect state transfer in products and covers of graphs, Linear Multilinear Algebra, 64, 235-246 (2015) · Zbl 1331.05141
[11] Cui, S.-Y.; Tian, G.-X., The signless laplacian spectrum of the (edge) corona of two graphs, Utilitas Math., 88, 287-297 (2012) · Zbl 1256.05137
[12] Cui, S.-Y.; Tian, G.-X., The spectrum and the signless laplacian spectrum of coronae, Linear Algebra Appl., 437, 1692-1703 (2012) · Zbl 1247.05135
[14] Cvetković, D.; Rowlinson, P.; Simić, S. K., Signless laplacians of finite graphs, Linear Algebra Appl., 423, 155-171 (2007) · Zbl 1113.05061
[15] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on the signless Laplacian, I, Publ. Inst. Math. (Beogr.), 85, 99, 19-33 (2009) · Zbl 1224.05293
[16] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on the signless Laplacian, II, Linear Algebra Appl., 432, 2257-2272 (2010) · Zbl 1218.05089
[17] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on the signless Laplacian, III, Appl. Anal. Discrete Math., 4, 156-166 (2010) · Zbl 1265.05360
[18] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Application (1980), Academic Press: Academic Press New York · Zbl 0458.05042
[19] Dam, E. R.V.; Haemers, W. H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[20] Das, K. C.; Liu, M. H., Kite graphs determined by their spectra, Appl. Math. Comput., 297, 74-78 (2017) · Zbl 1411.05158
[21] Estrada, E.; Benzi, M., Core-satellite graphs: clustering, assortativity and spectral properties, Linear Algebra Appl., 517, 30-52 (2017) · Zbl 1353.05078
[22] Gopalapillai, I., The spectrum of neighborhood corona of graphs, Kragujevac J. Math, 35, 493-500 (2011) · Zbl 1289.05283
[23] Gopalapillai, I., Spectrum of two new joins of graphs and infinite families of integral graphs, Kragujev. J. Math., 36, 133-139 (2012) · Zbl 1289.05296
[24] Grone, R.; Merris, R.; Sunder, V. S., The Laplacian spectral of graphs, SIAM J. Matrix Anal. Appl., 11, 218-239 (1990) · Zbl 0733.05060
[25] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0182.57702
[26] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0729.15001
[27] Hou, Y.; Shiu, W.-C., The spectrum of the edge corona of two graphs, Electron. J. Linear Algebra., 20, 586-594 (2010) · Zbl 1205.05144
[28] Lan, J.; Zhou, B., Spectra of graph operations based on \(r\)-graph, Linear Multilinear Algebra, 63, 1401-1422 (2015) · Zbl 1308.05073
[29] Li, X.; Shi, Y.; Gutman, I., Graph Energy (2012), Springer-Verlag: Springer-Verlag New York
[30] Liu, X.-G.; Lu, P.-L., Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae, Linear Algebra Appl., 438, 3547-3559 (2013) · Zbl 1261.05058
[31] Liu, X.-G.; Zhang, Z. H., Spectra of subdivision-vertex join and subdivision-edge join of two graphs, Bull. Malays. Math. Soc. (2017)
[32] Liu, X.-G.; Zhou, S.-M., Spectra of the neighbourhood corona of two graphs, Linear Multilinear Algebra, 62, 1205-1219 (2014) · Zbl 1302.05107
[34] Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197-198, 143-176 (1994) · Zbl 0802.05053
[35] McLeman, C.; McNicholas, E., Spectra of coronae, Linear Algebra Appl., 435, 998-1007 (2011) · Zbl 1221.05239
[36] Mieghem, P. V., Graph Spectra for Complex Networks (2011), Cambridge University Press: Cambridge University Press New York, USA · Zbl 1232.05128
[37] Nath, M.; Paul, S., On the spectra of graphs with edge-pockets, Linear Multilinear Algebra, 63, 509-522 (2015) · Zbl 1305.05133
[38] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010
[39] Tian, G.-X.; Huang, T.-Z.; Zhou, B., A note on sum of powers of the Laplacian eigenvalues of bipartite graphs, Linear Algebra Appl., 430, 2503-2510 (2009) · Zbl 1165.05020
[40] Wang, S.-L.; Zhou, B., The signless Laplacian spectra of the corona and edge corona of two graphs, Linear Multilinear Algebra, 61, 197-204 (2013) · Zbl 1259.05120
[41] Xie, P. C.; Zhang, Z. Z.; Comellas, F., On the spectrum of the normalized Laplacian of iterated triangulations of graphs, Appl. Math. Comput., 273, 1123-1129 (2016) · Zbl 1410.05143
[42] Xie, P. C.; Zhang, Z. Z.; Comellas, F., The normalized Laplacian spectrum of subdivisions of a graph, Appl. Math. Comput., 286, 250-256 (2016) · Zbl 1410.05144
[43] Zhang, M. J.; Li, S. C., On the signless Laplacian spectra of \(k\)-trees, Linear Algebra Appl., 467, 136-148 (2015) · Zbl 1304.05098
[44] Zhang, M. J.; Li, S. C., Extremal Halin graphs with respect to the signless Laplacian spectra, Discrete Appl. Math., 213, 207-218 (2016) · Zbl 1344.05077
[45] Zhang, H.; Yang, Y.; Li, C., Kirchhoff index of composite graphs, Discrete Appl. Math., 157, 2918-2927 (2009) · Zbl 1209.05149
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.