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 |