Spectral Characterizations of Some Distance-Regular Graphs
Edwin R. van Dam
and Willem H. Haemers
DOI: 10.1023/A:1013847004932
Abstract
When can one see from the spectrum of a graph whether it is distance-regular or not? We give some new results for when this is the case. As a consequence we find (among others) that the following distance-regular graphs are uniquely determined by their spectrum: The collinearity graphs of the generalized octagons of order (2,1), (3,1) and (4,1), the Biggs-Smith graph, the M 22 graph, and the coset graphs of the doubly truncated binary Golay code and the extended ternary Golay code.
Pages: 189–202
Keywords: distance regular graphs; eigenvalues; cospectral graphs
Full Text: PDF
References
1. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer, Heidelberg, 1989.
2. A.E. Brouwer and W.H. Haemers, “The Gewirtz graph: An exercise in the theory of graph spectra,” European J. Combin. 14 (1993), 397-407.
3. M.A. Fiol and E. Garriga, “From local adjacency polynomials to locally pseudo-distance-regular graphs,” J. Comb. Th. B. 71 (1997), 162-183.
4. D.G. Fon-Der-Flaass, “A distance-regular graph with intersection array {5, 4, 3, 3; 1, 1, 1, 2} does not exist,” J. Alg. Comb. 2 (1993), 49-56.
5. C.D. Godsil and B.D. McKay, “Constructing cospectral graphs,” Aequationes Mathematicae 25 (1982), 257- 268.
6. W.H. Haemers, “Distance-regularity and the spectrum of graphs,” Linear Alg. Appl. 236 (1996), 265-278.
7. W.H. Haemers and E. Spence, “Graphs cospectral with distance-regular graphs,” Linear Multilin. Alg. 39 (1995), 91-107.
8. A.J. Hoffman, “On the polynomial of a graph,” Amer. Math. Monthly 70 (1963), 30-36.
9. T. Huang and C. Liu, “Spectral characterization of some generalized odd graphs,” Graphs Comb. 15 (1999), 195-209.
2. A.E. Brouwer and W.H. Haemers, “The Gewirtz graph: An exercise in the theory of graph spectra,” European J. Combin. 14 (1993), 397-407.
3. M.A. Fiol and E. Garriga, “From local adjacency polynomials to locally pseudo-distance-regular graphs,” J. Comb. Th. B. 71 (1997), 162-183.
4. D.G. Fon-Der-Flaass, “A distance-regular graph with intersection array {5, 4, 3, 3; 1, 1, 1, 2} does not exist,” J. Alg. Comb. 2 (1993), 49-56.
5. C.D. Godsil and B.D. McKay, “Constructing cospectral graphs,” Aequationes Mathematicae 25 (1982), 257- 268.
6. W.H. Haemers, “Distance-regularity and the spectrum of graphs,” Linear Alg. Appl. 236 (1996), 265-278.
7. W.H. Haemers and E. Spence, “Graphs cospectral with distance-regular graphs,” Linear Multilin. Alg. 39 (1995), 91-107.
8. A.J. Hoffman, “On the polynomial of a graph,” Amer. Math. Monthly 70 (1963), 30-36.
9. T. Huang and C. Liu, “Spectral characterization of some generalized odd graphs,” Graphs Comb. 15 (1999), 195-209.