A new arithmetic criterion for graphs being determined by their generalized Q-spectrum

"Which graphs are determined by their spectrum (DS for short)?" is a fundamental question in spectral graph theory. It is generally very hard to show a given graph to be DS and few results about DS graphs are known in literature. In this paper, we consider the above problem in the context of the generalized Q-spectrum. A graph G is said to be determined by the generalized Q-spectrum (DGQS for short) if, for any graph H, H and G have the same Q-spectrum and so do their complements imply that H is isomorphic to G. We give a simple arithmetic condition for a graph being DGQS. More precisely, let G be a graph with adjacency matrix A and degree diagonal matrix D. Let Q = A + D be the signless Laplacian matrix of G, and W-Q(G) = [e, Qe, ..., Q(n-1) e] (e is the all-ones vector) be the Q-walk matrix. We show that if det W-Q(G)/2(left perpendicular3n-2/2right perpendicular) (which is always an integer) is odd and square-free, then G is DGQS. (C) 2018 Elsevier B.V. All rights reserved.