On perfect matchings, edge-colourings and eigenvalues of cubic graphs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908751229878272 |
|---|---|
| author | Haemers, Willem H. |
| author_facet | Haemers, Willem H. |
| contents | We discuss the question whether the existence of perfect matchings in a cubic graph can be seen from the spectrum of its adjacency matrix. For regular graphs in general and for three edge-disjoint perfect matchings in a cubic graph (that is, an edge colouring with three colors) the answer is known to be negative. In the latter case, a few counter examples (found by computer) are known. Here we show that these counter examples can be extended to an infinite family by use of truncation. Thus we obtain infinitely many pairs of cospectral cubic graphs with different edge-chromatic number. For all these pairs both graphs have a perfect matching, and the mentioned question is still open. But we do find a new sufficient condition for a perfect matching in a cubic graphs in terms of its spectrum. In addition we obtain a few more results concerning spectral characterizations of cubic graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03778 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On perfect matchings, edge-colourings and eigenvalues of cubic graphs Haemers, Willem H. Combinatorics 05C45, 05C50 We discuss the question whether the existence of perfect matchings in a cubic graph can be seen from the spectrum of its adjacency matrix. For regular graphs in general and for three edge-disjoint perfect matchings in a cubic graph (that is, an edge colouring with three colors) the answer is known to be negative. In the latter case, a few counter examples (found by computer) are known. Here we show that these counter examples can be extended to an infinite family by use of truncation. Thus we obtain infinitely many pairs of cospectral cubic graphs with different edge-chromatic number. For all these pairs both graphs have a perfect matching, and the mentioned question is still open. But we do find a new sufficient condition for a perfect matching in a cubic graphs in terms of its spectrum. In addition we obtain a few more results concerning spectral characterizations of cubic graphs. |
| title | On perfect matchings, edge-colourings and eigenvalues of cubic graphs |
| topic | Combinatorics 05C45, 05C50 |
| url | https://arxiv.org/abs/2601.03778 |