The smallest pair of cospectral cubic graphs with different chromatic indexes
From MaRDI portal
Publication:2065795
DOI10.1016/J.DAM.2021.12.016zbMATH Open1481.05057arXiv2112.06112OpenAlexW4212944934MaRDI QIDQ2065795FDOQ2065795
Authors: Zhidan Yan, Wei Wang 
Publication date: 13 January 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: Using an exhaustive search on cubic graphs of order 16, we find a unique cospectral pair with different chromatic indexes. This example indicates that the chromatic index of a regular graph is not characterized by its spectrum, which answers a question recently posed in [O. Etesami, W. H. Haemers, On NP-hard graph properties characterized by the spectrum, Discrete Appl. Math., 285(2020)526-529]. We prove that any orthogonal matrix representing the similarity between the two adjacency matrices of the cospectral pair cannot be rational. This implies that the cospectral pair cannot be obtained using the original GM-switching method or its generalizations based on rational orthogonal matrices.
Full work available at URL: https://arxiv.org/abs/2112.06112
Recommendations
- Constructing families of cospectral regular graphs
- Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
- Constructing cospectral graphs via regular rational orthogonal matrices with level two
- Enumeration of cospectral graphs.
- Cospectral regular graphs with and without a perfect matching
Cites Work
- Practical graph isomorphism. II.
- Cospectral graphs and regular orthogonal matrices of level 2
- Constructing cospectral graphs
- The NP-Completeness of Edge-Coloring
- The chromatic index of strongly regular graphs
- Cospectral pairs of regular graphs with different connectivity
- Cospectral regular graphs with and without a perfect matching
- Graphs cospectral with distance-regular graphs
- A note on non-\(\mathbb{R}\)-cospectral graphs
- Distance-regularity and the spectrum of graphs
- On NP-hard graph properties characterized by the spectrum
- Title not available (Why is that?)
- The Petersen graph is not 3-edge-colorable---a new proof
- Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
- The Petersen graph is not 1-factorable: postscript to `The Petersen graph is not 3-edge-colorable -- a new proof' [Discrete Math. 268 (2003) 325--326]
- Generalized cospectral graphs with and without Hamiltonian cycles
- On a theorem of Godsil and McKay concerning the construction of cospectral graphs
Uses Software
This page was built for publication: The smallest pair of cospectral cubic graphs with different chromatic indexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065795)
