TOPICS

# Distance-Regular Graph

A connected graph is distance-regular if for any vertices and of and any integers , 1, ... (where is the graph diameter), the number of vertices at distance from and distance from depends only on , , and the graph distance between and , independently of the choice of and .

In particular, a distance-regular graph is a graph for which there exist integers such that for any two vertices and distance , there are exactly neighbors of and neighbors of , where is the set of vertices of with (Brouwer et al. 1989, p. 434). The array of integers characterizing a distance-regular graph is known as its intersection array.

Distance regularity of a graph may be checked in the GRAPE package in GAP using the function IsDistanceRegular(G).

A disconnected graph is distance-regular iff it is a disjoint union of cospectral distance-regular graphs.

A deep theorem of Fiol and Garriga (1997) states that a graph is distance-regular iff for every vertex, the number of vertices at a distance (where is the number of distinct graph eigenvalues) equals an expression in terms of the spectrum (van Dam and Haemers 2003).

Classes of distance-regular graphs include complete graphs , complete bipartite graphs , complete tripartite graphs , cycle graphs (Brouwer et al. 1989, p. 1), empty graphs (trivially), Hadamard graphs (Brouwer et al. 1989, p. 19), hypercube graphs (Biggs 1993, p. 161), Kneser graphs , ladder rung graphs (trivially), odd graphs (Biggs 1993, p. 161), and Platonic graphs (Brouwer et al. 1989, p. 1).

A distance-regular graph with graph diameter is a strongly regular graph (Biggs 1993, p. 159), and connected distance-regular graphs are conformally rigid (Steinerberger and Thomas 2024).

Every distance-transitive graph is distance-regular, but the converse does not necessarily hold, as first shown by Adel'son-Vel'skii et al. (1969; Brouwer et al. 1989, p. 136). The smallest distance-regular graph that is not distance-transitive is the Shrikhande graph (Brouwer et al. 1989, p. 136) on 16 nodes.

All cubic distance-regular graphs are known (Biggs et al. 1986; Brouwer et al. 1989, p. 221; Royle), as illustrated above and summarized in the following table.

All quartic distance-regular graphs are known (Brouwer and Koolen 1999) except that there is one graph on the list (the generalized hexagon of order 3) which is not yet known to be uniquely determined by its intersection array (Koolen et al. 2023). In particular, any distance-regular graph of valency 4 has one of the 17 intersection arrays listed below (and hence is one of the 16 graphs described, or is the point-line incidence graph a generalized hexagon of order 3)

 No. graph intersection array spectrum 1. 5 1 pentatope graph 2. 6 2 octahedron graph 3. 8 2 complete bipartite graph 4. 9 2 generalized quadrangle 5. 10 3 crown graph 6. 14 3 nonincidence graph of Qt31 7. 15 3 line graph of the Petersen graph 8. 16 4 hypercube graph 9. 21 3 generalized hexagon 10. 26 3 incidence graph of 11. 32 4 incidence graph of minus parallel class 12. 35 3 odd graph 13. 45 4 generalized octagon 14. 70 7 Danzer graph 15. 80 4 -cage graph 16. 189 6 generalized dodecagon 17. 728 6 -cage graph

Koolen et al. (2023) enumerate 18 cases of non-geometric distance-regular graphs of diameter at least 3 with smallest graph eigenvalue at least , as summarized in the following table.

 case graph intersection array (a) odd graph (b) Sylvester graph (c) second subconstituent of the Hoffman-Singleton graph (d) Perkel graph (e) symplectic 7-cover of the complete graph (f) Coxeter graph (g) dodecahedral graph (h) Biggs-Smith graph (i) Wells graph (j) icosahedral graph (k) Hall graph (l) halved cube graph (m) Gosset graph (n) halved cube graph (o) 24-Klein graph (p) exactly two distance-regular graphs (q) more than one distance-regular graph (r) putative distance-regular graph

Note that the odd -cycle graphs with (which satisfy all the given criteria) are apparently silently omitted.

The following table summarizes some known distance-regular graphs, excluding a number of named families.

 graph intersection array 5 pentatope graph 6 octahedral graph 8 16-cell graph 9 generalized quadrangle (2,1) 12 icosahedral graph 14 quartic vertex-transitive graph Qt31 15 generalized quadrangle (2,2) 15 quartic vertex-transitive graph Qt39 16 Clebsch graph 16 Shrikhande graph 16 tesseract graph 21 (7,2)-Kneser graph 21 generalized hexagon (2,1) 22 (11,5,2)-incidence graph 22 (11,6,3)-incidence graph 24 Klein graph 25 25-Paulus graphs 26 (13,9,6)-incidence graph 26 26-Paulus graphs 26 (29,14,6,7)-strongly regular graphs (40) 26 (4,6)-cage 27 generalized quadrangle (2,4) 27 generalized quadrangle (2,4) minus spread 1 27 generalized quadrangle (2,4) minus spread 2 27 Schläfli graph 28 Chang graphs 28 (8,2)-Kneser graph 28 locally 13-Paley graph 30 (15,7,3)-incidence graph 32 (8,1)-Hadamard graph 32 Kummer graph 32 Wells graph 35 Grassmann graph 35 4-odd graph 36 hexacode graph 36 (9,2)-Kneser graph 36 Sylvester graph 38 (19,9,4)-incidence graph 42 (21,16,12)-incidence graph 42 (5,6)-cage 42 Hoffman-Singleton graph minus star 45 (10,2)-Kneser graph 45 generalized octagon (2,1) 45 halved Foster graph 46 (23,11,5)-incidence graph 48 (12,1)-Hadamard graph 50 Hoffman-Singleton graph 50 Hoffman-Singleton graph complement 52 generalized hexagon (3,1) 55 (11,2)-Kneser graph 56 distance 2-graph of the Gosset graph 56 Gewirtz graph 56 Gosset graph 57 Perkel graph 62 (31,15,7)-incidence graph 62 (31,25,20)-incidence graph 62 (6,6)-cage 63 (63,32,16,16)-strongly regular graph 63 symplectic 7-cover of 64 (1,1)-Doob graph 64 64-cyclotomic graph 65 Hall graph 66 (12,2)-Kneser graph 70 (35,17,8)-incidence graph 70 (7,3)-bipartite Kneser graph 70 (8,4)-Johnson graph 72 Suetake graph 74 (37,9,2)-incidence graph 77 M22 graph 78 (13,2)-Kneser graph 80 (40,13,4)-incidence graph 80 (4,8)-cage 81 Brouwer-Haemers graph 91 (14,2)-Kneser graph 94 (47,23,11)-incidence graph 100 bipartite double of the Hoffman-Singleton graph 100 cocliques in the Hoffman-Singleton graph 100 Hall-Janko graph 100 Higman-Sims graph 105 generalized hexagon (4,1) 112 bipartite double of the Gewirtz graph 112 generalized quadrangle (3,9) 114 (57,49,42)-incidence graph 114 (8,6)-cage 120 (120,56,28,24)-strongly regular graph 120 (120,63,30,36)-strongly regular graph 126 5-odd graph 126 (9,4)-Johnson graph 126 Zara graph 130 Grassmann graph 144 halved Leonard graph (2) 146 (73,64,56)-incidence graph 146 (9,6)-cage 154 bipartite double of the M22 graph 155 Grassmann graph 160 generalized octagon (2,1) 162 second subconstituent of the McLaughlin graph 162 local McLaughlin graph 162 van Lint-Schrijver graph 170 (5,8)-cage 170 (5,8)-cage 175 line graph of the Hoffman-Singleton graph 176 (176,70,18,34)-strongly regular graph 176 (176,105,68,54)-strongly regular graph 182 (10,6)-cage 186 generalized hexagon (5,1) 189 generalized dodecagon (2,1) 200 bipartite double of the Higman-Sims graph 210 (10,4)-Johnson graph 243 Berlekamp-van Lint-Seidel Graph 253 (253,112,36,60)-strongly regular graph 256 (1,2)-Doob graph 266 Livingstone Graph 275 McLaughlin graph 288 Leonard graph 312 (6,8)-cage 315 Hall-Janko near octagon 416 graph 425 generalized octagon (4,1) 462 6-odd graph 506 truncated Witt graph 651 Grassmann graph 759 large Witt graph 1024 (1,3)-Doob graph 1024 (2,1)-Doob graph 1170 (9,8)-cage 1395 Grassmann graph

Automorphic Graph, Biggs-Smith Graph, Coxeter Graph, Cubic Symmetric Graph, Cubical Graph, Desargues Graph, Distance-Transitive Graph, Dodecahedral Graph, Foster Graph, Global Parameters, Heawood Graph, Intersection Array, Moore Graph, Pappus Graph, Petersen Graph, Regular Graph, Shrikhande Graph, Sylvester Graph, Taylor Graph, Wells Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; and Faradžev, I. A. "Example of Graph without a Transitive Automorphism Group." Dokl. Akad. Nauk SSSR 185, 975-976, 1969. English version Soviet Math. Dokl. 10, 440-441, 1969.Bendito, E.; Carmona, A.; and Encinas, A. M. "Shortest Paths in Distance-Regular Graphs." Europ. J. Combin. 21, 153-166, 2000.Biggs, N.; Boshier, A.; and Shawe-Taylor, J. "Cubic Distance-Regular Graphs." J. London Math. Soc. S2-33, 385-394, 1986.Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 13 and 159, 1993.Brouwer, A. "The Cubic Distance-Regular Graphs." http://www.win.tue.nl/~aeb/graphs/cubic_drg.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.Brouwer, A. and Koolen, J. "The Distance-Regular Graphs of Valency Four." J. Algebraic Combin. 10, 5-24, 1999.Eppstein, D. "Cubic Symmetric xyz Graphs." Oct. 16, 2007. http://11011110.livejournal.com/120326.html.Fiol, M. A. and Garriga, E. "From Local Adjacency Polynomials to Locally Pseudo-Distance-Regular Graphs." J. Combin. Th. B 71, 162-183, 1997.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 68-69, 2001.Haemers, W. H. and Spence, E. "Graphs Cospectral with Distance-Regular Graphs." Linear Multilin. Alg. 39, 91-107, 1995.Haemers, W. H. "Distance-Regularity and the Spectrum of Graphs." Linear Alg. Appl. 236, 265-278, 1996.Koolen, J. H.; Yu, K.; Liang, X.; Choi, H.; and Markowsky, G. "Non-Geometric Distance-Regular Graphs of Diameter at Least 3 With Smallest Eigenvalue at Least ." 15 Nov 2023. https://arxiv.org/abs/2311.09001.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Distance-Regular Graphs" http://school.maths.uwa.edu.au/~gordon/remote/foster/#drgs.Steinerberger, S. and Thomas, R. R. "Conformally Rigid Graphs." 19 Feb 2024. https://arxiv.org/abs/2402.11758.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

## Referenced on Wolfram|Alpha

Distance-Regular Graph

## Cite this as:

Weisstein, Eric W. "Distance-Regular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Distance-RegularGraph.html