Let $ G(a_1, a_2, \ldots, a_k) $ be a simple graph with vertex set $ V(G) = V_1\cup V_2\cup \cdots \cup V_k $ and edge set $ E(G) = \{(u, v)|u\in V_i, v\in V_{i+1}, i = 1, 2, \ldots, k-1\} $, where $ |V_i| = a_i > 0 $ for $ 1\leq i\leq k $ and $ V_i\cap V_j = \emptyset $ for $ i\neq j $. Given two positive integers $ k $ and $ n $, and $ k-2 $ positive rational numbers $ t_2, t_3, \ldots, t_{\lceil k/2\rceil} $ and $ t_2', t_3', \ldots, t_{\lfloor k/2\rfloor}' $, let $ \Upsilon(n; k)_t^{t'} = \{G(a_1, a_2, \ldots, a_k)|\sum_{i = 1}^ka_i = n, a_{2i-1} = t_{i}a_1, a_{2j} = t_j'a_2, i = 2, 3, \ldots, \lceil k/2\rceil, $ $ j = 2, 3, \ldots, \lfloor k/2\rfloor; t = (t_2, t_3, \ldots, t_{\lceil k/2\rceil}), t' = (t_2', t_3', \ldots, t_{\lfloor k/2\rfloor}'); a_s\in N, 1\leq s\leq k\} $, where $ N $ is the set of positive integers. In this paper, we prove that all graphs in $ \Upsilon(n; k)_t^{t'} $ are cospectral with respect to the normalized Laplacian if it is not an empty set.
Citation: Meiling Hu, Shuli Li. Cospectral graphs for the normalized Laplacian[J]. AIMS Mathematics, 2022, 7(3): 4061-4067. doi: 10.3934/math.2022224
Let $ G(a_1, a_2, \ldots, a_k) $ be a simple graph with vertex set $ V(G) = V_1\cup V_2\cup \cdots \cup V_k $ and edge set $ E(G) = \{(u, v)|u\in V_i, v\in V_{i+1}, i = 1, 2, \ldots, k-1\} $, where $ |V_i| = a_i > 0 $ for $ 1\leq i\leq k $ and $ V_i\cap V_j = \emptyset $ for $ i\neq j $. Given two positive integers $ k $ and $ n $, and $ k-2 $ positive rational numbers $ t_2, t_3, \ldots, t_{\lceil k/2\rceil} $ and $ t_2', t_3', \ldots, t_{\lfloor k/2\rfloor}' $, let $ \Upsilon(n; k)_t^{t'} = \{G(a_1, a_2, \ldots, a_k)|\sum_{i = 1}^ka_i = n, a_{2i-1} = t_{i}a_1, a_{2j} = t_j'a_2, i = 2, 3, \ldots, \lceil k/2\rceil, $ $ j = 2, 3, \ldots, \lfloor k/2\rfloor; t = (t_2, t_3, \ldots, t_{\lceil k/2\rceil}), t' = (t_2', t_3', \ldots, t_{\lfloor k/2\rfloor}'); a_s\in N, 1\leq s\leq k\} $, where $ N $ is the set of positive integers. In this paper, we prove that all graphs in $ \Upsilon(n; k)_t^{t'} $ are cospectral with respect to the normalized Laplacian if it is not an empty set.
| [1] |
M. Aouchiche, P. Hansen, Cospectrality of graphs with respect to distance matrices, Appl. Math. Comput., 325 (2018), 309–321. https://doi.org/10.1016/j.amc.2017.12.025 doi: 10.1016/j.amc.2017.12.025
|
| [2] |
R. B. Bapat, M. Karimi, Construction of cospectral integral regular graphs, Discuss. Math. Graph Theory, 37 (2017), 595–609. https://doi.org/10.7151/dmgt.1960 doi: 10.7151/dmgt.1960
|
| [3] |
S. Butler, A note about cospectral graphs for the adjacency and normalized Laplacian matrices, Linear Multilinear Algebra, 58 (2010), 387–390. https://doi.org/10.1080/03081080902722741 doi: 10.1080/03081080902722741
|
| [4] |
S. Butler, J. Grout, A construction of cospectral graphs for the normalized Laplacian, Electron. J. Combin., 18 (2011), 231. https://doi.org/10.37236/718 doi: 10.37236/718
|
| [5] |
S. Butler, K. Heysse, A cospectral family of graphs for the normalized Laplacian found by toggling, Linear Algebra Appl., 507 (2016), 499–512. https://doi.org/10.1016/j.laa.2016.06.033 doi: 10.1016/j.laa.2016.06.033
|
| [6] |
S. Butler, Using twins and scaling to construct cospectral graphs for the normalized Laplacian, Electron. J. Linear Algebra, 28 (2015), 54–68. https://doi.org/10.13001/1081-3810.2989 doi: 10.13001/1081-3810.2989
|
| [7] | F. R. K. Chung, Spectral graph theory, CBMS Lecture Notes, AMS, Providence, RI, 1997. |
| [8] |
E. R. van Dam, W. H. Haemers, J. H. Koolen, Cospectral graphs and the generalized adjacency matrix, Linear Algebra Appl., 423 (2007), 33–41. https://doi.org/10.1016/j.laa.2006.07.017 doi: 10.1016/j.laa.2006.07.017
|
| [9] |
C. Delorme, Eigenvalues of complete multipartite graphs, Discrete Math., 312 (2012), 2532–2535. https://doi.org/10.1016/j.disc.2011.07.018 doi: 10.1016/j.disc.2011.07.018
|
| [10] | C. D. Godsil, B. McKay, Products of graphs and their spectra, In: L. R. A. Casse, W. D. Wallis, Combinatorial mathematics IV, Lecture Notes in Mathematics, Springer, 560 (1976), 61–72. https://doi.org/10.1007/BFb0097369 |
| [11] |
C. D. Godsil, B. McKay, Constructing cospectral graphs, Aeq. Math., 25 (1982), 257–268. https://doi.org/10.1007/BF02189621 doi: 10.1007/BF02189621
|
| [12] |
W. H. Haemers, E. Spence, Enumeration of cospectral graphs, European J. Combin., 25 (2004), 199–211. https://doi.org/10.1016/S0195-6698(03)00100-8 doi: 10.1016/S0195-6698(03)00100-8
|
| [13] |
C. R. Johnson, M. Newman, A note on cospectral graphs, J. Combin. Theory, Ser. B, 28 (1980), 96–103. https://doi.org/10.1016/0095-8956(80)90058-1 doi: 10.1016/0095-8956(80)90058-1
|
| [14] |
M. R. Kannan, S. Pragada, On the construction of cospectral graphs for the adjacency and the normalized Laplacian matrices, Linear Multilinear Algebra, 2020, 1–22. https://doi.org/10.1080/03081087.2020.1821594 doi: 10.1080/03081087.2020.1821594
|
| [15] |
K. Lorenzen, Cospectral constructions for several graph matrices using cousin vertices, Spec. Matrices, 10 (2022), 9–22. https://doi.org/10.1515/spma-2020-0143 doi: 10.1515/spma-2020-0143
|
| [16] |
M. Langberg, D. Vilenchik, Constructing cospectral graphs via a new form of graph product, Linear Multilinear Algebra, 66 (2018), 1838–1852. https://doi.org/10.1080/03081087.2017.1373733 doi: 10.1080/03081087.2017.1373733
|
| [17] |
R. Merris, Large families of Laplacian isospectral graphs, Linear Multilinear Algebra, 43 (1997), 201–205. https://doi.org/10.1080/03081089708818525 doi: 10.1080/03081089708818525
|
| [18] | S. Osborne, Cospectral bipartite graphs for the normalized Laplacian, Ph. D. Thesis, Iowa State University, 2013. |
| [19] |
J. S. Tan, On isospectral graphs, Interdiscip. Inform. Sci., 4 (1998), 117–124. https://doi.org/10.4036/iis.1998.117 doi: 10.4036/iis.1998.117
|
Figures(1)
Meiling Hu, Shuli Li. Cospectral graphs for the normalized Laplacian[J]. AIMS Mathematics, 2022, 7(3): 4061-4067. doi: 10.3934/math.2022224
DownLoad: