# 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.

##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C45 Eulerian and Hamiltonian graphs 15A18 Eigenvalues, singular values, and eigenvectors
Full Text:
##### References:
  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  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  Catlin, P. A.; Lai, H. J., Supereulerian graph and the Petersen graph, J. Combin. Theory Ser. B, 66, 123-139 (1996) · Zbl 0839.05070  Cvetković, D. M.; Rowlinson, P.; Simić, S. K., An Introduction to the Theory of Graph Spectra (2010), Cambridge University Press: Cambridge University Press Cambridge  van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079  van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586 (2009) · Zbl 1205.05156  Godsil, C. D.; Royle, G., Algebraic Combinatorics (2001), Springer-Verlag: Springer-Verlag New York  Haemers, W. H.; Spence, E., Enumeration of cospectral graphs, European J. Combin., 25, 199-211 (2004) · Zbl 1033.05070  Johnson, C. R.; Newman, M., A note on cospectral graphs, J. Combin. Theory Ser. B, 28, 96-103 (1980) · Zbl 0431.05021  Schwenk, A. J., Almost all trees are cospectral, (New Directions in the Theory of Graphs (1973), Academic Press), 275-307 · Zbl 0261.05102  Schwenk, A. J.; Wilson, R. J., On the eigenvalues of a graph, (Selected Topics in Graph Theory, vol. 1 (1978), Academic Press), 307-336  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.