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 , Q e , … , Q n − 1 e ] ( e is the all-ones vector) be the Q -walk matrix. We show that if det W Q ( G ) 2 ⌊ 3 n − 2 2 ⌋ (which is always an integer) is odd and square-free, then G is DGQS.