For an $n$-vertex graph $G$, the walk matrix of $G$, denoted by $W(G)$, is the matrix $[e,A(G)e,\ldots,(A(G))^{ n-1}e]$, where $A(G)$ is the adjacency matrix of $G$ and $e$ is the all-ones vector. For two integers $m$ and $\ell$ with $1\le \ell\le (m+1)/2$, let $G\circ P_m^{ (\ell)}$ be the rooted product of $G$ and the path $P_m$ taking the $\ell$-th vertex of $P_m$ as the root, i.e., $G\circ P_m^{ (\ell)}$ is a graph obtained from $G$ and $n$ copies of the path $P_m$ by identifying the $i$-th vertex of $G$ with the $\ell$-th vertex (the root vertex) of the $i$-th copy of $P_m$ for each $i$. We prove that, $\det W(G\circ P_m^{ (\ell)})$ equals $\pm (\det A(G))^{ \lfloor\frac{ m}{ 2}\rfloor}(\det W(G))^m$ if $\gcd(\ell,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 $\ell=1$. As a direct application, we prove that if $G$ satisfies $\det A(G)=\pm 1$ and $\det W(G)=\pm 2^{ \lfloor n/2\rfloor}$, then for any sequence of integer pairs $(m_i,\ell_i)$ with $\gcd(\ell_i,m_i+1)=1$ for each $i$, all the graphs in the family \begin{ equation*} G\circ P_{ m_1}^{ (\ell_1)}, (G\circ P_{ m_1}^{ (\ell_1)})\circ P_{ m_2}^{ (\ell_2)}, ((G\circ P_{ m_1}^{ (\ell_1)})\circ P_{ m_2}^{ (\ell_2)})\circ P_{ m_3}^{ (\ell_3)},\ldots \end{ equation*} are determined by their generalized spectrum.

Categories: math.CO

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