×

The smallest pair of cospectral cubic graphs with different chromatic indexes. (English) Zbl 1481.05057

Summary: 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 and W. H. Haemers, ibid. 285, 526–529 (2020; Zbl 1447.05122)]. 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.

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1447.05122

Software:

SageMath; Traces; nauty
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Abiad, B. Brimkov, J. Breen, T.R. Cameron, H. Gupta, R.R. Villagrán, Constructions of cospectral graphs with different zero forcing numbers, arXiv:2111.12343.
[2] Abiad, A.; Haemers, W. H., Cospectral graphs and regular orthogonal matrices of level 2, Electron. J. Combin., 19, #P13 (2012) · Zbl 1253.05092
[3] Blázsik, Z. L.; Cummings, J.; Haemers, W. H., Cospectral regular graphs with and without a perfect matching, Discrete Math., 338, 199-201 (2015) · Zbl 1305.05186
[4] Cioabă, S. M.; Guo, K.; Haemers, W. H., The chromatic index of strongly regular graphs, Ars Math. Contemp., 20, 187-194 (2021) · Zbl 1485.05184
[5] Etesami, O.; Haemers, W. H., On NP-hard graph properties characterized by the spectrum, Discrete Appl. Math., 285, 526-529 (2020) · Zbl 1447.05122
[6] Filar, J. A.; Gupta, A.; Lucas, S. K., Connected cospectral graphs are not necessarily both Hamiltonian, Aust. Math. Soc. Gaz., 32, 193 (2005) · Zbl 1110.05318
[7] Godsil, C. D.; McKay, B. D., Constructing cospectral graphs, Aequationes Math., 25, 257-268 (1982) · Zbl 0527.05051
[8] Haemers, W. H., Distance-regularity and the spectrum of graphs, Linear Algebra Appl., 236, 265-278 (1996) · Zbl 0845.05101
[9] Haemers, W. H., Cospectral pairs of regular graphs with different connectivity, Discuss. Math. Graph Theory, 40, 577-584 (2020) · Zbl 1433.05195
[10] Haemers, W. H.; Spence, E., Graphs cospectral with distance-regular graphs, Linear Multilinear Algebra, 39, 91-107 (1995) · Zbl 0831.05045
[11] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034
[12] Liu, F.; Wang, W., A note on non-\( \mathbb{R} \)-cospectral graphs, Electron. J. Combin., 24, #48 (2017) · Zbl 1358.05175
[13] Liu, F.; Wang, W.; Yu, T.; Lai, H.-J., Generalized cospectral graphs with and without Hamiltonian cycles, Linear Algebra Appl., 585, 199-208 (2020) · Zbl 1426.05104
[14] Mckay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112 (2014) · Zbl 1394.05079
[15] Naserasr, R.; Škrekovski, R., The Petersen graph is not 3-edge-colorable-a new proof, Discrete Math., 268, 325-326 (2003) · Zbl 1022.05029
[16] Qiu, L.; Ji, Y.; Wang, W., On a theorem of Godsil and McKay concerning the construction of cospectral graphs, Linear Algebra Appl., 603, 265-274 (2020) · Zbl 1446.05060
[17] SageMath, the Sage Mathematics Software System (Version 8.9), The sage developers (2019), https://www.sagemath.org
[18] Volkmann, L., 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], Discrete Math., 287, 193-194 (2004) · Zbl 1053.05054
[19] Wang, W.; Qiu, L.; Hu, Y., Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\), Linear Algebra Appl., 563, 154-177 (2019) · Zbl 1405.05108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.