On the Enumeration of Generalized Cospectral Mates of Graphs

Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas · 2026

Read On the Enumeration of Generalized Cospectral Mates of Graphs by Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-07373.txt.

Introduction

Muhammad Raza and co-authors posted a 2026 arXiv preprint. The preprint deals with enumeration of generalized cospectral mates of graphs. It came out on arXiv in 2026 as a PAPERS preprint. The work investigates the enumeration of generalized cospectral mates of simple graphs. Where the generalized spectrum consists of the spectra 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. Readers in the field get a short, focused account of the problem and the steps the authors take.

Catalog record

CREATORMuhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-07373

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Enumeration of Generalized Cospectral Mates of Graphs Muhammad Raza, Obaid Ullah Ahmad, Mudassir Shabbir, Waseem Abbas Abstract This paper investigates the enumeration of generalized cospectral mates of simple graphs, where the generalized spectrum consists of the spectra 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 (SNF) of the walk matrix W ⁡ ( G ) W(G) , which lead to a tight upper bound on the number of generalized cospectral mates of a graph. Our upper bound applies to a much broader class of graphs than those previously shown to have no generalized cospectral mates (determined by generalized spectrum). Consequently, this work extends the family of graphs for which strong and informative spectral uniqueness results are available. Keywords : Adjacency matrix, Walk matrix, Cospectral graphs, Generalized spectrum 1 Introduction Let G=(V,E) be a simple graph with n vertices, meaning it is finite, undirected, and contains no loops or multiple edges. The adjacency matrix A(G) is the n\times n symmetric matrix where each entry a_{ij}=1 if vertices v_{i} and v_{j} are adjacent, and a_{ij}=0 otherwise. The spectrum of a graph G , denoted \operatorname{Spec}(G) , is the multiset of eigenvalues of its adjacency matrix A(G) , counted with algebraic multiplicity. Two graphs G and H are isomorphic , denoted G\cong H , if there exists a bijection f:V(G)\to V(H) such that vertices u and v are adjacent in G if and only if f(u) and f(v) are adjacent in H . In other words, isomorphic graphs have identical structure, differing only by a relabeling of vertices. The complement of a graph G , denoted \overline{G} , is the graph on the same vertex set where two vertices are adjacent if and only if they are not adjacent in G . The adjacency matrix of the complement is given by A(\overline{G})=J-I-A(G) , where J is the n\times n all-ones matrix and I is the identity matrix. A graph G is said to be determined by its spectrum (DS) if every graph with the same spectrum as G is isomorphic to G . A central open question in spectral graph theory is: “Which graphs are DS?” This question was first raised by Günthard and Primas [ 2 ] in the context of chemistry and is closely related to Kac’s famous question [ 4 ] , “Can one hear the shape of a drum?” Fisher [ 1 ] modeled the drum as a graph whose sound is described by its spectrum, linking Kac’s question to the graph being DS. Haemers conjectured that almost all graphs are DS [ 9 , 3 ] . Nevertheless, proving that a given graph is DS remains challenging; see [ 9 , 10 ] for surveys. Wang and Xu [ 13 ] considered this problem in the context of generalized spectrum , defined as the pair (\operatorname{Spec}(G),\operatorname{Spec}(\overline{G})) . Two or more graphs are generalized cospectral if they have the same generalized spectrum. While isomorphic graphs are clearly generalized cospectral, the converse does not hold in general. Non-isomorphic graphs that are generalized cospectral are referred to as generalized cospectral mates . A graph is said to be determined by its generalized spectrum (DGS) if it has no generalized cospectral mate. Recent advances have leveraged the properties of the walk matrix to address these questions. For a graph G with n vertices, the walk matrix W(G) is the n\times n matrix with columns e,\,A(G)e,\,\dots,\,A(G)^{n-1}e , where e is the all-ones column vector of length n . A graph G is controllable if W(G) is non-singular. Wang [ 11 ] introduced a large family of controllable graphs and proved that all graphs in this family are DGS. Extending these ideas to oriented graphs, Qiu et al. [ 6 ] introduced a family of oriented graphs determined by their generalized skew spectra. A natural extension of this line of research addresses a fundamental question: how many generalized cospectral mates can a graph have? Wang et al. [ 14 ] identified a family of graphs where each graph has at most one generalized cospectral mate and proposed an algorithm to find such a mate. Later on, they provided an algorithm to find generalized cospectral mates for controllable or almost controllable graphs [ 12 ] . However, the practical feasibility of this algorithm is constrained by the computational difficulty of factorizing large integers. In the context of oriented graphs, Raza et al. [ 8 ] and Lin et al. [ 5 ] independently established upper bounds on the number of their generalized cospectral mates for a large family. In this paper, we introduce a large family of graphs and establish an upper bound on the number of their generalized cospectral mates. Let d_{1}(M)\mid d_{2}(M)\mid\dots\mid d_{n}(M) denote the invariant factors of the Smith Normal Form of a matrix M . We define \mathcal{F}_{n} as the family of controllable graphs on n vertices where each graph G satisfies: d_{\lceil n/2\rceil}(W(G))=1\quad\text{and}\quad d_{n-1}(W(G))=2. (1) To analyze the relationship between generalized cospectral mates in \mathcal{F}_{n} , we utilize the concept of the level of a rational matrix: Definition 1 . The level of a rational matrix Q , denoted \ell(Q) , is defined as the smallest positive integer x such that xQ is an integral matrix. For graphs in \mathcal{F}_{n} , we prove the following theorem: Theorem 1 . Let G\in\mathcal{F}_{n} , and let H_{1} and H_{2} be graphs that are generalized cospectral with G . Let Q_{1} and Q_{2} be the rational orthogonal matrices satisfying Q_{i}^{T}A(G)Q_{i}=A(H_{i}) and Q_{i}e=e for i=1,2 . If \ell(Q_{1})=\ell(Q_{2}) , then H_{1}\cong H_{2} . We will later establish the existence of the orthogonal matrices referenced in Theorem 1 . This theorem shows that, for graphs in \mathcal{F}_{n} , each possible level of a rational orthogonal matrix yields at most one generalized cospectral mate. Consequently, the number of generalized cospectral mates is bounded above by the number of possible levels: Theorem 2 . Let G\in\mathcal{F}_{n} . Let d_{n}(W(G))=\prod_{j=1}^{m}p_{j}^{k_{j}} be the prime factorization of the last invariant factor of the walk matrix W(G) . Then G can have at most \left(\prod_{j=1}^{m}k_{j}\right)-1 generalized cospectral mates. We begin by reviewing essential preliminaries in Section 2 . In Section 3 , we investigate the properties of a specific set of orthogonal matrices; these properties establish the framework for proving our main results in Section 4 . We then provide illustrative examples and numerical analysis in Section 5 to demonstrate the application of our results. Section 6 concludes the paper with a summary of our findings and potential directions for future research. 2 Preliminaries In this section, we review the essential results required for the proofs of Theorem 1 and 2 . A matrix Q is called regular if Qe=e where e is the all-ones column vector. The following theorem characterizes graphs sharing the same generalized spectrum: Theorem 3 . [ 13 ] Let G be a controllable graph and H be a graph generalized cospectral with G . Then H must be controllable and there exists a

Read the complete text