Generalized Spectral Characterization of Graphs Revisited

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,⋯,Aⁿ⁻¹e] (e is the all-one vector) be its walk-matrix. Denote by Gₙ the set of all graphs on n vertices with (W)≠ 0. We define a large family of graphs Fₙ=∈Gₙ|(W)2/2is square-free and 2/2+1|(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∈ Fₙ, if there is a rational orthogonal matrix Q with $Qe=e$ such that QTAQ 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 Fₙ are DGS.