Generalized Spectral Characterization of Graphs Revisited

Abstract

A graph $G$ is said to be determined by its generalized spectrum (DGS for short) if for any graph $H$, $H$ and $G$ are cospectral with cospectral complements implies that $H$ is isomorphic to $G$. Wang and Xu (2006) gave some methods for determining whether a family of graphs are DGS. In this paper, we shall review some of the old results and present some new ones along this line of research.

More precisely, let $A$ be the adjacency matrix of a graph $G$, and let $W=[e,Ae,\cdots,A^{n-1}e]$ ($e$ is the all-one vector) be its walk-matrix. Denote by $\mathcal{G}_n$ the set of all graphs on $n$ vertices with $\det(W)\neq 0$. We define a large family of graphs $$\mathcal{F}_n=\{G\in{\mathcal{G}_n}|\frac{\det(W)}{2^{\lfloor
n/2\rfloor}}\mbox{is square-free and }2^{\lfloor
n/2\rfloor+1}\not|\det(W)\}$$ (which may have positive density among all graphs, as suggested by some numerical experiments). The main result of the paper shows that for any graph $G\in {\mathcal{F}_n}$, if there is a rational orthogonal matrix $Q$ with $Qe=e$ such that $Q^TAQ$ is a (0,1)-matrix, then $2Q$ must be an integral matrix (and hence, $Q$ has well-known structures). As a consequence, we get the conclusion that almost all graphs in $\mathcal{F}_n$ are DGS.