An improved condition for a graph to be determined by its generalized spectrum

Abstract

A fundamental and challenging problem in spectral graph theory is to characterize which graphs are uniquely determined by their spectra. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author proved that an $n$-vertex graph $G$ is uniquely determined by its generalized spectrum (DGS) whenever $2^{-\lfloor \frac{n}{2}\rfloor }\det W$ is odd and square-free. Here, $W$ is the walk matrix of $G$, namely, $W=[e,Ae,\dots ,A^{n-1}e]$ with $e$ all-one vector and $A$ the adjacency matrix of $G$. In this paper, we focus on a larger family of graphs with $d_n$ square-free, where $d_n$ refers to the last invariant factor of $W$. We introduce a new kind of polynomials for a graph $G$ associated with a prime $p$. Such a polynomial is invariant under generalized cospectrality. Using the newly defined polynomials, we obtain a sufficient condition for a graph in the larger family to be DGS. The main result of this paper improves upon the aforementioned result of Wang while the proof for the main result gives a new way to attack the problem of generalized spectral characterization of graphs.

14 pages

Cited by in corpus (2)

• Haemers' conjecture: an algorithmic perspective
• The Smith normal form of the walk matrix of the Dynkin graph $D_n$ for $n\equiv 0(\mathrm{mod}4)$