On the Number of Generalized Cospectral Mates of Graphs
Abstract
Two graphs are called generalized cospectral if they share the same spectrum and their complements also share the same spectrum. A longstanding problem in spectral graph theory asks: which graphs are determined by their generalized spectrum (DGS)? This work takes a more quantitative approach — rather than asking whether the answer is unique, we ask how many non-isomorphic generalized cospectral mates a graph can have.
We establish an explicit upper bound on this count using arithmetic constraints derived from the Smith Normal Form (SNF) of the walk matrix. The bound is determined by the number of distinct odd prime factors of the walk matrix determinant, and applies to a substantially broader class of graphs than those previously known to be DGS. This extends the family of graphs for which strong spectral-uniqueness results are available.
Keywords: Adjacency matrix · Walk matrix · Cospectral graphs · Generalized spectrum · Smith Normal Form
Key Result
For a graph G in the family ℋₙ, the number of non-isomorphic generalized cospectral mates is bounded above by a quantity determined by the arithmetic structure of det W(G) — specifically, the number of distinct odd prime divisors of the normalized determinant. This gives a tight arithmetic criterion that goes well beyond DGS/non-DGS binary classification.
Collaboration
| Author | Affiliation | Role |
| Muhammad Raza (corresponding) |
Dept. of Computer Science, LUMS, Lahore |
Primary contributor; walk-matrix framework |
| Obaid Ullah Ahmad |
Dept. of Electrical Engineering, UT Dallas |
Spectral analysis; SNF computations |
| Mudassir Shabbir |
Dept. of Computer Science, LUMS, Lahore |
Graph-theoretic structure; combinatorial bounds |
| Waseem Abbas |
Dept. of Systems Engineering, UT Dallas |
NSF-funded PI; network controllability connections |
Supported in part by NSF Grant No. 2325416 (Abbas, Ahmad).
Background
The question of whether a graph is determined by its spectrum originates with Günthard and Primas (1956) in the context of Hückel molecular orbital theory, and was famously popularized by Kac’s question “Can one hear the shape of a drum?” (1966). Wang and collaborators introduced walk-matrix techniques that gave arithmetic sufficiency conditions for a graph to be DGS; this work builds directly on those results and sharpens them into quantitative bounds.