Counting cospectral graphs obtained via switching
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915529665544192 |
|---|---|
| author | Abiad, Aida Van de Berg, Nils Simoens, Robin |
| author_facet | Abiad, Aida Van de Berg, Nils Simoens, Robin |
| contents | Switching is an operation on a graph that does not change the spectrum of the adjacency matrix, thus producing cospectral graphs. An important activity in the field of spectral graph theory is the characterization of graphs by their spectrum. Hence, switching provides a tool for disproving the existence of such a characterization.
This paper presents a general framework for counting the number of graphs that have a non-isomorphic cospectral graph through a switching method, expanding on the work by Haemers and Spence [European Journal of Combinatorics, 2004]. Our framework is based on a different counting approach, which allows it to be used for all known switching methods for the adjacency matrix. From this, we derive asymptotic results, which we complement with computer enumeration results for graphs up to $10$ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_08627 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting cospectral graphs obtained via switching Abiad, Aida Van de Berg, Nils Simoens, Robin Combinatorics Switching is an operation on a graph that does not change the spectrum of the adjacency matrix, thus producing cospectral graphs. An important activity in the field of spectral graph theory is the characterization of graphs by their spectrum. Hence, switching provides a tool for disproving the existence of such a characterization. This paper presents a general framework for counting the number of graphs that have a non-isomorphic cospectral graph through a switching method, expanding on the work by Haemers and Spence [European Journal of Combinatorics, 2004]. Our framework is based on a different counting approach, which allows it to be used for all known switching methods for the adjacency matrix. From this, we derive asymptotic results, which we complement with computer enumeration results for graphs up to $10$ vertices. |
| title | Counting cospectral graphs obtained via switching |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.08627 |