Title | ||
---|---|---|
A new arithmetic criterion for graphs being determined by their generalized Q-spectrum |
Abstract | ||
---|---|---|
“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 WQ(G)=[e,Qe,…,Qn−1e] (e is the all-ones vector) be the Q-walk matrix. We show that if detWQ(G)2⌊3n−22⌋ (which is always an integer) is odd and square-free, then G is DGQS. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.disc.2018.08.008 | Discrete Mathematics |
Keywords | Field | DocType |
Spectra of graphs,Cospectral graphs,Determined by spectrum,Q-spectrum | Adjacency matrix,Integer,Discrete mathematics,Laplacian matrix,Graph,Combinatorics,Spectral graph theory,Matrix (mathematics),Arithmetic,Isomorphism,Diagonal matrix,Mathematics | Journal |
Volume | Issue | ISSN |
342 | 10 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lihong Qiu | 1 | 0 | 0.34 |
Yizhe Ji | 2 | 0 | 0.34 |
Wei Wang | 3 | 81 | 12.64 |