Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-08T03:25:31.506Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructing families of cospectral regular graphs

Part of: Graph theory

Published online by Cambridge University Press:  30 June 2020

M. Haythorpe  and
A. Newcombe
M. Haythorpe
Affiliation:
Flinders University, 1284 South Road, Tonsley, SA 5042, Australia
A. Newcombe*
Affiliation:
Flinders University, 1284 South Road, Tonsley, SA 5042, Australia
*
*Corresponding author. Emails: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A set of graphs are called cospectral if their adjacency matrices have the same characteristic polynomial. In this paper we introduce a simple method for constructing infinite families of cospectral regular graphs. The construction is valid for special cases of a property introduced by Schwenk. For the case of cubic (3-regular) graphs, computational results are given which show that the construction generates a large proportion of the cubic graphs, which are cospectral with another cubic graph.

MSC classification

Primary: 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Secondary: 05C07: Vertex degrees
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 5 , September 2020 , pp. 664 - 671
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Research partially supported by ARC Discovery Grant DP150100618.

References

Abiad, A. and Haemers, W. H. (2012) Cospectral graphs and regular orthogonal matrices of level 2. Electron. J. Combin. 19 13–29.CrossRefGoogle Scholar
Baniasadi, P., Ejov, V., Filar, J. A. and Haythorpe, M. (2016) Genetic Theory for Cubic Graphs, Springer Briefs inOperations Research, Springer.Google Scholar
Bapat, R. B. and Karimi, M. (2016) Construction of cospectral regular graphs. Mat. Vesnik 68 66–76.Google Scholar
Blazsik, Z. L., Cummings, J. and Haemers, W. H. (2015) Cospectral regular graphs with and without a perfect matching. Discrete Math. 338 199–201.CrossRefGoogle Scholar
Borkar, V. S., Ejov, V., Filar, J. A. and Nguyen, G. T. (2012) Hamiltonian Cycle Problem and Markov Chains, Springer Science & Business Media.CrossRefGoogle Scholar
Cvetkovic, D., Rowlinson, P. and Simic, S. (1997) Eigenspaces of Graphs, Cambridge University Press.CrossRefGoogle Scholar
Filar, J. A., Gupta, A. and Lucas, S. K. (2005) Connected cospectral graphs are not necessarily both Hamiltonian. Aust. Math. Soc. Gaz. 32 193.Google Scholar
Godsil, C. D. (1992) Walk generating functions, Christophell–Darboux identities and the adjacency matrix of a graph. Combin. Probab. Comput. 1 13–25.CrossRefGoogle Scholar
Godsil, C. D. and McKay, B. D. (1982) Construction of cospectral graphs. Aequationes Math. 25 257–268.CrossRefGoogle Scholar
Rowlinson, P. (1993) The characteristic polynomials of modified graphs. Discrete Appl. Math. 67 209–219.CrossRefGoogle Scholar
Schwenk, A. J. (1979) Removal-cospectral sets of vertices in a graph. In 10th Southeastern International Conference on Combinatorics, Graph Theory and Computing, pp. 849–860.Google Scholar