Generalized spectral characterization of graphs revisited

Wei Wang¹

¹Xi'an Jiaotong University

The electronic journal of combinatorics, Tome 20 (2013) no. 4

Résumé

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^{\lfloorn/2\rfloor}}\mbox{is square-free and }2^{\lfloorn/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.

Détail

DOI : 10.37236/3748

Classification : 05C50
Mots-clés : spectra of graphs, cospectral graphs, determined by spectrum