Generation of isospectral graphs. (English) Zbl 0932.05053
Authors’ abstract: We discuss a discrete version of Sunada’s theorem on isospectral manifolds, which allows the generation of isospectral simple graphs, i.e. nonisomorphic simple graphs that have the same Laplace spectrum. We also consider additional boundary conditions and Buser’s transplantation technique applied to a discrete situation.
Reviewer: Dragos Cvetković (Beograd)
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Botti, J Graph Theory 17 pp 467– (1993) |
| [2] | ?Spectral geometry and the Cheeger constant,? Expanding graphs, DIMACS Ser Discrete Math Theoret Comput Sci 10, Princeton, NJ, 1992, pp. 5-19. |
| [3] | Buser, Ann Inst Fourier Grenobl 36 pp 167– (1986) · Zbl 0579.53036 · doi:10.5802/aif.1054 |
| [4] | Buser, Internat Math Res Notic 9 pp 391– (1994) |
| [5] | Chapman, Amer Math Mont 102 pp 124– (1995) |
| [6] | and Spectra of graphs, Academic, New York, 1979. |
| [7] | Eichinger, Macromo 13 pp 1– (1980) |
| [8] | Forsman, J Chem Phys 65 pp 4111– (1976) |
| [9] | Grone, SIAM J Matrix Anal Appl 11 pp 218– (1990) |
| [10] | Grone, SIAM J Discrete Math 7 pp 221– (1994) |
| [11] | Gutman, J Chem Phys 68 pp 1321– (1978) |
| [12] | McKay, Ars Combin 3 pp 219– (1977) |
| [13] | ?The Laplacian spectrum of graphs,? Graph theory, combinatorics, and applications, Vol 2, Wiley, New York, 1991, pp. 871-898. · Zbl 0840.05059 |
| [14] | Rowlinson, Univ Beograd Publ Elektrotehn Fak Ser Mat 3 pp 67– (1992) |
| [15] | ?Almost all trees are cospectral,? New directions in the theory of graphs, Academic, New York, 1973, pp. 275-307. |
| [16] | Sunada, Ann Math 121 pp 169– (1985) |
| [17] | Turner, SIAM J Appl Math 16 pp 520– (1968) |
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.
