Distance-regular graph

Graph families defined by their automorphisms
distance-transitive	${\displaystyle {\boldsymbol {\rightarrow }}}$	distance-regular	${\displaystyle {\boldsymbol {\leftarrow }}}$	strongly regular
${\displaystyle {\boldsymbol {\downarrow }}}$
symmetric (arc-transitive)	${\displaystyle {\boldsymbol {\leftarrow }}}$	t-transitive, t ≥ 2		skew-symmetric
${\displaystyle {\boldsymbol {\downarrow }}}$
(if connected) vertex- and edge-transitive	${\displaystyle {\boldsymbol {\rightarrow }}}$	edge-transitive and regular	${\displaystyle {\boldsymbol {\rightarrow }}}$	edge-transitive
${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$
vertex-transitive	${\displaystyle {\boldsymbol {\rightarrow }}}$	regular	${\displaystyle {\boldsymbol {\rightarrow }}}$	(if bipartite) biregular
${\displaystyle {\boldsymbol {\uparrow }}}$
Cayley graph	${\displaystyle {\boldsymbol {\leftarrow }}}$	zero-symmetric		asymmetric

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and i = d(v, w).

By considering the special case k = 1, one sees that in a distance-regular graph, for any two vertices v and w at distance i, the number of neighbors of w that are at distance j from v is the same. Conversely, it turns out that this special case implies the full definition of distance-regularity. Therefore, an equivalent definition is that a distance-regular graph is a regular graph for which there exist integers b_i,c_i,i=0,...,d such that for any two vertices x,y with y in G_i(x), there are exactly b_i neighbors of y in G_i-1(x) and c_i neighbors of y in G_i+1(x), where G_i(x) is the set of vertices y of G with d(x,y)=i (Brouwer et al., p. 434). The array of integers characterizing a distance-regular graph is known as its intersection array.

Every distance-transitive graph is distance regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group.

A distance-regular graph with diameter 2 is strongly regular, and conversely (unless the graph is disconnected).

It is usual to use the following notation for a distance-regular graph G. The number of vertices is n. The number of neighbors of w (that is, vertices adjacent to w) whose distance from v is i, i + 1, and i − 1 is denoted by a_i, b_i, and c_i, respectively; these are the intersection numbers of G. Obviously, a₀ = 0, c₀ = 0, and b₀ equals k, the degree of any vertex. If G has finite diameter, then d denotes the diameter and we have b_d = 0. Also we have that a_i+b_i+c_i= k

...
Wikipedia