A characterization of distance-regular graphs with diameter three. (English) Zbl 0874.05060

van Dam, Edwin R.; Haemers, Willem H.

J. Algebr. Comb. 6, No. 3, 299-303 (1997).

Summary: We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph.

MSC:

05E30	Association schemes, strongly regular graphs
05C75	Structural characterization of families of graphs
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
05C12	Distance in graphs

Keywords:

eigenvalues of graphs; strongly regular graphs; distance-regular graphs; diameter; distance; spectrum

References:

[1]	A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik 3.18, Springer, Heidelberg, 1989.
[2]	van Dam, E. R., Regular graphs with four eigenvalues, Linear Algebra Appl., 226-228, 139-162, (1995) · Zbl 0839.05072
[3]	E.R. van Dam, “Bounds on special subsets in graphs, eigenvalues and association schemes,” J. Alg. Combin. (to appear). · Zbl 0974.05052
[4]	E.R. van Dam, “Graphs with few eigenvalues—An interplay between combinatorics and algebra,” Thesis, Tilburg University, Center dissertation series 20, 1996.
[5]	Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616, (1995) · Zbl 0831.05044
[6]	Haemers, W. H., “Distance-regularity and the spectrum of graphs, Linear Algebra Appl., 236, 265-278, (1996) · Zbl 0845.05101
[7]	Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36, (1963) · Zbl 0112.14901