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

作者：Qiu, Lihong; Ji, Yizhe; Wang, Wei^*

来源：Discrete Mathematics, 2019, 342(10): 2770-2782.

DOI：10.1016/j.disc.2018.08.008

• Spectra of graphs
• Cospectral graphs
• Determined by spectrum
• 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.

• 出版日期2019-10
• 单位西安交通大学