🔢 mathematics

On the number of generalized cospectral mates of graphs

This paper establishes a tight upper bound on the number of generalized cospectral mates for simple graphs by utilizing arithmetic constraints from the Smith Normal Form of the walk matrix, thereby extending spectral uniqueness results to a broader class of graphs than previously possible.

Original authors: Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to identify a suspect based on their "fingerprint." In the world of mathematics, graphs (which are just networks of dots connected by lines) have fingerprints called spectra.

Usually, if two graphs have the same spectrum, they are considered "twins." But here's the catch: sometimes, two completely different-looking graphs (non-isomorphic) can have the exact same spectrum. It's like two different houses having the exact same floor plan and room sizes, but one has a blue door and the other has a red door.

The Problem: Too Many Twins?

For a long time, mathematicians asked: "Can we tell these graphs apart?"

The Old Way: Look at the graph's spectrum. (Sometimes this works, sometimes it doesn't).
The New Way (Generalized Spectrum): Look at the graph's spectrum AND the spectrum of its "opposite" (the complement graph, where every connection that existed is now broken, and every broken connection is now a link).

This "Generalized Spectrum" is a much stronger fingerprint. It's like checking the house's floor plan and the blueprint of the empty lot it sits on. Most of the time, this is enough to prove two graphs are identical. But sometimes, a few "imposter" graphs still sneak through.

The Big Question: If a graph does have imposters, how many can there be? Is it just one? Ten? A million?

The Solution: The "Walk Matrix" and the "Smith Normal Form"

The authors of this paper, Muhammad Raza and his team, came up with a clever way to count these imposters without having to find every single one.

Here is their approach, broken down with analogies:

1. The Walk Matrix: The Graph's "Memory"

Imagine a person walking through the graph. They start at a random spot and take steps to neighbors, then neighbors of neighbors, and so on.
The Walk Matrix is a record of all these possible paths. It captures the "memory" of how the graph is connected.

If the graph is "controllable," this memory is unique and powerful. It means the graph's structure is rigid and hard to fake.

2. The Smith Normal Form: The "Prime Code"

When mathematicians look at the Walk Matrix, they can break it down into a special code called the Smith Normal Form (SNF).
Think of the SNF as the prime factorization of the graph's DNA. Just as any number can be broken down into prime numbers (like $12 = 2 \times 2 \times 3$ ), the Walk Matrix breaks down into a list of "invariant factors."
The authors focus on the last number in this list. This number holds the secret to how many imposters exist.

3. The "Level" of the Imposter

To turn one graph into its imposter, you need a special mathematical "key" (a matrix).
The authors define the Level of this key. Think of the Level as the "size" or "complexity" of the key needed to unlock the transformation.

Key Insight: The paper proves that if two imposters require keys of the same size (Level), they are actually the same graph (just with the dots relabeled).
Therefore, to count the imposters, you just need to count how many different sizes of keys are possible.

The Big Discovery (The Upper Bound)

The team found a family of graphs (let's call them the "Fn Family") where the rules are very strict. For these graphs, the number of possible imposters is limited by the prime factors of that last number in the Smith Normal Form.

The Formula in Plain English:
If the last number in the code breaks down into prime factors like this:
$2^3 \times 3^2 \times 5^1$
(Which means $2 \times 2 \times 2 \times 3 \times 3 \times 5$ )

The number of possible imposters is calculated by taking the exponents (3, 2, and 1), adding 1 to each, multiplying them, and subtracting 1 (because one of the "keys" is the graph itself).

$(3+1) \times (2+1) \times (1+1) - 1 = 4 \times 3 \times 2 - 1 = 23$ .
So, this graph can have at most 23 imposters.

Why This Matters

It's a Limit, Not a Guess: Before this, we didn't have a hard ceiling on how many imposters a graph could have. Now, we have a mathematical "speed limit."
It Works for Many Graphs: The authors tested this on thousands of random graphs. They found that about 39% of all random graphs fall into this special "Fn Family" where this rule applies. That's a huge chunk of the graph world!
Real-World Proof: They built a specific graph with 10 dots. Their math predicted it could have at most 3 imposters. They then used a computer to find them, and exactly 3 existed. The math was perfect.

Summary

Think of the graph as a unique puzzle.

Old View: "If the pieces look the same, it's the same puzzle." (Sometimes wrong).
New View: "If the pieces and the box design look the same, it's the same puzzle." (Usually right).
This Paper: "If it's not the same puzzle, here is the maximum number of different puzzles that could possibly fool us, and here is exactly how to calculate that number just by looking at the puzzle's 'prime number code'."

This work turns a vague question ("How many look-alikes are there?") into a precise calculation, giving mathematicians a powerful new tool to understand the hidden structure of networks.

1. Problem Statement

The paper addresses a quantitative extension of a classical problem in spectral graph theory: determining how many non-isomorphic graphs share the same generalized spectrum.

Generalized Spectrum: Defined as the pair $(\text{Spec}(G), \text{Spec}(\bar{G}))$ , consisting of the spectrum of a graph $G$ and its complement $\bar{G}$ .
Generalized Cospectral Mates: A set of pairwise non-isomorphic graphs that share the same generalized spectrum.
The Core Question: While it is known that some graphs are "Determined by their Generalized Spectrum" (DGS) (i.e., they have zero mates), the paper seeks to establish explicit upper bounds on the number of generalized cospectral mates for graphs that are not uniquely determined. Previous work had provided algorithms to find mates but lacked general theoretical bounds on the count of such mates for broad classes of graphs.

2. Methodology

The authors employ a combination of linear algebra, number theory, and combinatorial matrix theory. The approach relies heavily on the Walk Matrix and its Smith Normal Form (SNF).

Key Definitions and Tools

Walk Matrix ( $W(G)$ ): An $n \times n$ matrix with columns $e, A(G)e, \dots, A(G)^{n-1}e$ , where $e$ is the all-ones vector. A graph is controllable if $W(G)$ is non-singular.
Rational Orthogonal Matrices: If two graphs $G$ and $H$ are generalized cospectral and controllable, there exists a unique regular rational orthogonal matrix $Q$ (where $Qe=e$) such that $Q^T A(G) Q = A(H)$ .
Level ( $\ell(Q)$ ): The smallest positive integer $x$ such that $xQ$ is an integral matrix. This is a crucial arithmetic parameter.
Smith Normal Form (SNF): For an integral matrix $M$ , the SNF is a diagonal matrix $\text{diag}(d_1, \dots, d_n)$ where $d_i | d_{i+1}$ . The $d_i$ are the invariant factors.

Theoretical Framework

The methodology proceeds through the following logical steps:

Arithmetic Constraints: The authors analyze the arithmetic properties of the rational orthogonal matrices $Q$ that relate generalized cospectral graphs. They utilize the SNF of the walk matrix to derive divisibility conditions on the level $\ell(Q)$ .
Rank Analysis over Finite Fields: They investigate the rank of the walk matrix over finite fields $\mathbb{F}_p$ . Specifically, they show that for certain graphs, the rank constraints force the columns of the scaled matrix $\ell(Q)Q$ to be scalar multiples of a fixed vector modulo $p^k$ .
Uniqueness via Level: They prove that if two graphs $H_1$ and $H_2$ are generalized cospectral to $G$ and their corresponding matrices $Q_1, Q_2$ have the same level, then $H_1$ and $H_2$ must be isomorphic. This reduces the problem of counting mates to counting the number of admissible levels.
Bounding Admissible Levels: By analyzing the prime factorization of the last invariant factor of the walk matrix, $d_n(W(G))$ , they determine the maximum number of distinct levels possible.

3. Key Contributions

A. Definition of Family $\mathcal{F}_n$

The authors define a specific family of controllable graphs, $\mathcal{F}_n$ , characterized by specific constraints on the invariant factors of their walk matrices:
$d_{\lceil n/2 \rceil}(W(G)) = 1 \quad \text{and} \quad d_{n-1}(W(G)) = 2$
This family is significant because it is large enough to include many random graphs but structured enough to allow for tight arithmetic bounds.

B. Theorem 1.1: Level Uniqueness

Statement: For any graph $G \in \mathcal{F}_n$ , if two generalized cospectral mates $H_1$ and $H_2$ correspond to rational orthogonal matrices $Q_1$ and $Q_2$ with the same level ( $\ell(Q_1) = \ell(Q_2)$ ), then $H_1 \cong H_2$ .
Significance: This establishes a one-to-one mapping (up to isomorphism) between the level of the transformation matrix and the isomorphism class of the mate.

C. Theorem 1.2: Explicit Upper Bound

Statement: Let $G \in \mathcal{F}_n$ and let the prime factorization of the last invariant factor of its walk matrix be $d_n(W(G)) = \prod_{j=1}^m p_j^{k_j}$ . The number of generalized cospectral mates of $G$ is at most:
$\left( \prod_{j=1}^m k_j \right) - 1$
Derivation: The bound is derived by counting the number of possible divisors of the invariant factors that satisfy the rank constraints over finite fields, excluding the trivial case where the level is 1 (which corresponds to the graph itself).

4. Results and Numerical Analysis

Tight Example: The authors constructed a specific graph $G$ $G$ with $n=10$ $n = 10$ vertices belonging to $\mathcal{F}_{10}$ $F_{10}$ .
- The last invariant factor was $d_{10}(W(G)) = 19350 = 2^1 \cdot 3^2 \cdot 5^2 \cdot 43^1$ .
- The exponents are $k_1=1, k_2=2, k_3=2, k_4=1$ .
- The theoretical upper bound is $(1 \times 2 \times 2 \times 1) - 1 = 3$ .
- Experimental Verification: A brute-force search confirmed that $G$ has exactly 3 generalized cospectral mates ( $H_1, H_2, H_3$ ). The levels of the corresponding matrices were found to be 3, 15, and 5, confirming they are distinct and match the theoretical prediction.
Statistical Prevalence: The authors generated 10,000 random graphs for various orders $n$ $n$ (from 11 to 50) with edge probability $p=0.5$ $p = 0.5$ .
- They found that approximately 39% of these random graphs belong to the family $\mathcal{F}_n$ .
- This indicates that the derived upper bound is applicable to a substantial and non-trivial portion of the space of simple graphs.

5. Significance and Future Directions

Quantitative Advancement: The paper moves beyond the binary question of "Is a graph DGS?" to the quantitative question "How many mates can a graph have?" providing a concrete, computable upper bound.
Broad Applicability: Unlike previous results that applied only to graphs with no mates, this work provides bounds for a large class of graphs that do have mates.
Methodological Innovation: The use of the Smith Normal Form and modular arithmetic constraints on rational orthogonal matrices offers a powerful new toolset for spectral graph theory, linking algebraic number theory directly to graph isomorphism problems.
Future Work: The authors suggest relaxing the constraints on the invariant factors to cover more graphs, extending the techniques to other matrices (e.g., signless Laplacian, distance matrix), and exploring different control vectors beyond the all-ones vector $e$ .

In summary, this paper provides a rigorous arithmetic framework to bound the number of generalized cospectral mates, demonstrating that for a large family of graphs, the number of such mates is strictly limited by the prime factorization of the determinant of the walk matrix's invariant factors.