Generalized spectral characterization of graphs revisited

. In cite{WX,WX1}, Wang and Xu 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.

Review text

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.

Recommendations

Cites work

Cited in

(61)

This page was built for publication: Generalized spectral characterization of graphs revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396911)