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

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.


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
Full Text: DOI


[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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.