Proof of a conjecture on the determinant of the walk matrix of rooted product with a path

Abstract

The walk matrix of an n-vertex graph G with adjacency matrix A, denoted by $W(G)$, is $[e,\mathrm{Ae},\dots ,A^{n-1}e]$, where e is the all-ones vector. Let $G\circ P_m$ be the rooted product of G and a rooted path $P_m$ (taking an endvertex as the root), i.e. $G\circ P_m$ is a graph obtained from G and n copies of $P_m$ by identifying each vertex of G with an endvertex of a copy of $P_m$. Mao et al. [A new method for constructing graphs determined by their generalized spectrum. Linear Algebra Appl. 2015;477:112–127.] and Mao and Wang [Generalized spectral characterization of rooted product graphs. Linear Multilinear Algebra. 2022. DOI:10.1080/03081087.2022.2098226.] proved that, for m = 2 and $m\in \{3,4\}$, respectively $detW(G\circ P_m)=\pm a_0^{\lfloor \frac{m}{2}\rfloor }(detW(G){)}^m,$ where $a_0$ is the constant term of the characteristic polynomial of G. Furthermore, in the same paper, Mao and Wang conjectured that the formula holds for any $m\ge 2$. In this paper, we verify this conjecture using the technique of Chebyshev polynomials.

Keywords:

• Walk matrix
• rooted product graph
• generalized spectral characterization

AMS Classification:

• 05C50

Acknowledgments

The authors thank Terrence Tao for providing an elegant proof of the crucial Lemma 6 and giving us permission to reproduce it in this paper. The authors would like to thank the editor and the anonymous reviewers for their helpful and detailed suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is supported by the National Natural Science Foundation of China (Grant Nos. 12001006 and 12101379), Natural Science Basic Research Plan in Shannxi Province of China (Grant No. 2020JQ-696) and the Scientific Research Foundation of Anhui Polytechnic University (Grant No. 2019YQQ024).