On the determinant of the walk matrix of the rooted product with a path

2025/03/15 by Yan, Zhidan, Wang, Wei
#05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2503.12130

Abstract

For an n-vertex graph G, the walk matrix of G, denoted by W(G), is the matrix [e,A(G)e,…,(A(G))^n-1e], where A(G) is the adjacency matrix of G and e is the all-ones vector. For two integers m and ℓ with 1≤ ℓ≤ (m+1)/2, let G∘ P_m^(ℓ) be the rooted product of G and the path P_m taking the ℓ-th vertex of P_m as the root, i.e., G∘ P_m^(ℓ) is a graph obtained from G and n copies of the path P_m by identifying the i-th vertex of G with the ℓ-th vertex (the root vertex) of the i-th copy of P_m for each i. We prove that, det W(G∘ P_m^(ℓ)) equals ± (det A(G))^{\lfloor(m)/(2)\rfloor}(det W(G))^m if gcd(ℓ,m+1)=1, and equals 0 otherwise. This extends a recent result established in [Wang et al. Linear Multilinear Algebra 72 (2024): 828--840] which corresponds to the special case ℓ=1. As a direct application, we prove that if G satisfies det A(G)=± 1 and det W(G)=± 2^{\lfloor n/2\rfloor}, then for any sequence of integer pairs (m_i,ℓ_i) with gcd(ℓ_i,m_i+1)=1 for each i, all the graphs in the family G∘ P_m1^(ℓ₁), (G∘ P_m1^(ℓ₁))∘ P_m2^(ℓ₂), ((G∘ P_m1^(ℓ₁))∘ P_m2^(ℓ₂))∘ P_m3^(ℓ₃),… are determined by their generalized spectrum.

Related

• Unlocking the walk matrix of a graph
• Matrix-Forest Theorems
• On the walk matrix of the Dynkin graph D_n
• Primary decomposition theorem and generalized spectral characterization of graphs
• New families of graphs determined by their generalized spectrum