Generalized spectral characterization of graphs revisited (Q396911)

Summary: 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\). \textit{W. Wang} and \textit{C.-X. Xu} [Linear Algebra Appl. 418, No. 1, 62--74 (2006; Zbl 1105.05050)] 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,\dots,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}\mid\frac{\det(W)}{2^{\lfloor n/2\rfloor}}\quad\text{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.