On the number of generalized cospectral mates of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914412699320320 |
|---|---|
| author | Raza, Muhammad Ahmad, Obaid Ullah Shabbir, Mudassir Abbas, Waseem |
| author_facet | Raza, Muhammad Ahmad, Obaid Ullah Shabbir, Mudassir Abbas, Waseem |
| contents | 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 (SNF) of the walk matrix, which leads 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 (graphs determined by generalized spectrum). Consequently, this work extends the family of graphs for which strong and informative spectral uniqueness results are available |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_07373 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the number of generalized cospectral mates of graphs Raza, Muhammad Ahmad, Obaid Ullah Shabbir, Mudassir Abbas, Waseem Combinatorics Rings and Algebras 05C50 G.2.2 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 (SNF) of the walk matrix, which leads 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 (graphs determined by generalized spectrum). Consequently, this work extends the family of graphs for which strong and informative spectral uniqueness results are available |
| title | On the number of generalized cospectral mates of graphs |
| topic | Combinatorics Rings and Algebras 05C50 G.2.2 |
| url | https://arxiv.org/abs/2601.07373 |