zbMATH — the first resource for mathematics

Generalized cospectral graphs with and without Hamiltonian cycles. (English) Zbl 1426.05104
Summary: The spectrum \(\sigma(G)\) of a graph \(G\) consists of all the eigenvalues (together with their multiplicities) of its adjacency matrix \(A(G)\). Two graphs \(G\) and \(H\) are called generalized cospectral if both \(\sigma(G) = \sigma(H)\) and \(\sigma(\overline{G}) = \sigma(\overline{H})\), where \(\overline{G} (\overline{H})\) is the complement of \(G (H)\). In this paper, we generalize the notion “cospectrally-rooted” to “\(k\)-cospectrally-rooted”, and obtain two equivalent statements for \(k\)-(generalized) cospectrally-rooted graphs. Furthermore, we have constructed two families of generalized cospectral graphs such that graphs in one of these two families are Hamiltonian and graphs in the other family are not Hamiltonian.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C45 Eulerian and Hamiltonian graphs
15A18 Eigenvalues, singular values, and eigenvectors
Full Text: DOI
[1] 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
[2] Abiad, A.; Haemers, W. H., Cospectral graphs and regular orthogonal matrices of level 2, Electron. J. Combin., 19, 3, Article P13 pp. (2012) · Zbl 1253.05092
[3] Catlin, P. A.; Lai, H. J., Supereulerian graph and the Petersen graph, J. Combin. Theory Ser. B, 66, 123-139 (1996) · Zbl 0839.05070
[4] Cvetković, D. M.; Rowlinson, P.; Simić, S. K., An Introduction to the Theory of Graph Spectra (2010), Cambridge University Press: Cambridge University Press Cambridge
[5] van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[6] van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586 (2009) · Zbl 1205.05156
[7] Godsil, C. D.; Royle, G., Algebraic Combinatorics (2001), Springer-Verlag: Springer-Verlag New York
[8] Haemers, W. H.; Spence, E., Enumeration of cospectral graphs, European J. Combin., 25, 199-211 (2004) · Zbl 1033.05070
[9] Johnson, C. R.; Newman, M., A note on cospectral graphs, J. Combin. Theory Ser. B, 28, 96-103 (1980) · Zbl 0431.05021
[10] Schwenk, A. J., Almost all trees are cospectral, (New Directions in the Theory of Graphs (1973), Academic Press), 275-307 · Zbl 0261.05102
[11] Schwenk, A. J.; Wilson, R. J., On the eigenvalues of a graph, (Selected Topics in Graph Theory, vol. 1 (1978), Academic Press), 307-336
[12] West, D. B., Introduction to Graph Theory (2000), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.