Constructing families of cospectral regular graphs. (English) Zbl 1462.05226
Summary: 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 A. J. Schwenk [Congr. Numerantium 24, 849–860 (1979; Zbl 0422.05035)]. 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:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C07 | Vertex degrees |
| 05C75 | Structural characterization of families of graphs |
Citations:
Zbl 0422.05035References:
| [1] | Abiad, A. and Haemers, W. H. (2012) Cospectral graphs and regular orthogonal matrices of level 2. Electron. J. Combin.1913-29. · Zbl 1253.05092 |
| [2] | Baniasadi, P., Ejov, V., Filar, J. A. and Haythorpe, M. (2016) Genetic Theory for Cubic Graphs, Springer Briefs inOperations Research, Springer. · Zbl 1330.05003 |
| [3] | Bapat, R. B. and Karimi, M. (2016) Construction of cospectral regular graphs. Mat. Vesnik6866-76. · Zbl 1461.05119 |
| [4] | Blazsik, Z. L., Cummings, J. and Haemers, W. H. (2015) Cospectral regular graphs with and without a perfect matching. Discrete Math.338199-201. · Zbl 1305.05186 |
| [5] | Borkar, V. S., Ejov, V., Filar, J. A. and Nguyen, G. T. (2012) Hamiltonian Cycle Problem and Markov Chains, Springer Science & Business Media. · Zbl 1246.90001 |
| [6] | Cvetkovic, D., Rowlinson, P. and Simic, S. (1997) Eigenspaces of Graphs, Cambridge University Press. · Zbl 0878.05057 |
| [7] | Filar, J. A., Gupta, A. and Lucas, S. K. (2005) Connected cospectral graphs are not necessarily both Hamiltonian. Aust. Math. Soc. Gaz.32193. · Zbl 1110.05318 |
| [8] | Godsil, C. D. (1992) Walk generating functions, Christophell-Darboux identities and the adjacency matrix of a graph. Combin. Probab. Comput.113-25. |
| [9] | Godsil, C. D. and Mckay, B. D. (1982) Construction of cospectral graphs. Aequationes Math.25257-268. · Zbl 0527.05051 |
| [10] | Rowlinson, P. (1993) The characteristic polynomials of modified graphs. Discrete Appl. Math.67209-219. |
| [11] | 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. · Zbl 0422.05035 |
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.
