Generalized Cospectral Mates — Ring-Theoretic Extension
About This Work
This repository contains the working manuscript for an extension of our results on generalized cospectral mates. While the main paper (Graph-Distinguishability—Journal) establishes upper bounds via the Smith Normal Form of the walk matrix, this companion work explores connections to ring-theoretic structure — specifically how the arithmetic of the underlying integer ring constrains the multiplicity of generalized cospectral mates.
Abstract
This paper establishes an upper bound on the number of generalized cospectral mates of simple graphs, where the generalized spectrum consists of the spectrum of a graph and its complement. Moving beyond the classical problem of identifying graphs determined by their generalized spectrum, we address the more quantitative question of how many non-isomorphic graphs can share the same generalized spectrum.
Our approach is based on arithmetic constraints derived from the Smith Normal Form of the walk matrix, which leads to a tight upper bound on the number of generalized cospectral mates of a graph. The bound applies to a much broader class of graphs than those previously shown to be DGS, extending 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 Insight
The walk matrix W(G) lives naturally in a free module over ℤ. Its Smith Normal Form diagonalizes it over ℤ, and the elementary divisors encode exactly the arithmetic obstructions to having many cospectral mates. Treating this through the lens of ring theory over ℤ/pℤ illuminates why prime factors of det W(G) control the number of generalized cospectral mates.
Collaboration
| Author | Affiliation |
| Muhammad Raza |
Dept. of Computer Science, LUMS, Lahore |
| Obaid Ullah Ahmad |
Dept. of Electrical Engineering, UT Dallas |
| Mudassir Shabbir |
Dept. of Computer Science, LUMS, Lahore |
| Waseem Abbas |
Dept. of Systems Engineering, UT Dallas |