Cospectral graphs for the normalized Laplacian

Abstract

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.

Keywords

• normalized laplacian
• cospectral
• tridiagonal matrix
• normalized laplacian characteristic polynomial