Generalized spectral characterizations of regular graphs based on graph-vectors (Q2685385)

The spectrum of a graph is the multiset of eigenvalues of its adjacency matrix. Clearly, isomorphic graphs have the same spectra, but the converse is not necessarily true: for example, the \(5\)-vertex star is co-spectral with its complement. A natural question, studied since the 1950s, is which graphs are determined (up to isomorphism) by their spectrum, or DS for short. While many classes of DS and non-DS graphs are known, it is not known how common this property is. A weaker, but still natural, property is determined by the spectra of the graph and its complement. This is equivalent to the statement that the graph is determined by the bivariate polynomial giving the value of the determinant of an arbitrary linear combination of the adjacency matrix, the identity, and the matrix \(ee^T\), where \(e\) is the all-ones vector. Previously \textit{W. Wang} [J. Comb. Theory, Ser. B 122, 438--451 (2017; Zbl 1350.05098)] gave a nice sufficient condition for this property. The walk matrix of an \(n\)-vertex graph \(G\) has columns \(e, Ae, \ldots, A^{n-1}e\). Its determinant is always of the form \(2^{\lfloor n/2\rfloor}k\) for some integer \(k\). A sufficient condition is for \(k\) to be odd and square-free. However, in the important case of regular graphs the determinant vanishes and so this result does not give any information. The purpose of this paper is to prove a similar result for regular graphs. Replacing the vector \(e\) by an arbitrary ``graph vector'' \(\xi\) (essentially, an integer vector defined in some automorphism-invariant way), one can ask whether the corresponding bivariate polynomial determines the graph. Replacing \(e\) by \(\xi\) gives a modified walk matrix, and the main result is that if this matrix satisfies a similar determinant condition then the graph is determined up to isomorphism. Several examples are given for particular choices of graph vectors on randomly generated regular graphs where this condition is satisfied, and numerical data supporting the supposition that such graphs are not too rare is provided. The disadvantage is perhaps that the property for a particular form of graph vector does not arise so naturally as for the all-ones vector.