A graph is distance transitive if its automorphism group is transitive on pairs of vertices at each pairwise distance in the graph. Distance-transitivity is a generalization of distance-regularity.
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).
While it is most common to consider only connected distance-transitive graphs, the above definition applies equally well to disconnected graphs, where in addition to integer graph distances, pairs of vertices in different connected components are considered to be at distance infinity.
There are finitely many distance-transitive graphs of each given vertex degree (Brouwer et al. 1989, pp. 214 and 220). Furthermore, all distance-transitive graphs with vertex degree are known (Brouwer et al. 1989, pp. 221-225), as listed in the following tables.
The numbers of distance-transitive graphs on , 2, ... vertices are 1, 2, 2, 4, 3, 7, 3, 9, 6, 11, ... (OEIS A308601) which agrees with the numebr of symmetric graphs up to . The smallest graph that is symmetric but not distance-transitive is the circulant graph .
Several commonly encountered families of graphs are distance-transitive, although in reality, graphs possessing this property are actually quite rare (Biggs 1993, p. 158).
Families of distance-transitive graphs include:
1. bipartite Kneser graphs (i.e., bipartite doubles of the odd graphs ),
3. complete bipartite graphs ,
4. complete graphs ,
5. complete k-partite graphs ,
6. crown graphs ,
7. empty graphs ,
8. folded cube graphs ,
9. Grassmann graphs ,
10. halved cube graphs ,
11. hypercube graphs ,
12. Johnson graphs ,
13. ladder rung graphs ,
14. odd graphs (Brouwer et al. 1989, p. 222, Theorem 7.5.2),
15. Paley graphs,
16. rook graphs ,
17. rook complement graphs ,
18. tetrahedral Johnson graphs , and
19. triangular graphs .
The connected distance-transitive graphs or order three are summarized by the following table.
The connected distance-transitive graphs of order 4 are summarized by the following table (Brouwer et al. 1989, p. 222).
graph | intersection array | |
6 | complete graph | |
10 | complete bipartite graph | |
12 | crown graph | |
12 | icosahedral graph | |
16 | Clebsch graph | |
22 | Levi graph of 2-(11,5,2) design | |
32 | 5-hypercube graph | |
32 | Wells graph | |
36 | Sylvester graph | |
42 | (5,6)-cage graph | |
= generalized hexagon | ||
50 | minus a parallel class | |
126 | odd graph | |
170 | (5,8)-cage graph | |
= generalized octagon | ||
252 | bipartite Kneser graph | |
= bipartite double of the odd graph |
The connected distance-transitive graphs of order 6 are summarized by the following table (Brouwer et al. 1989, p. 223).
graph | intersection array | |
7 | complete graph | |
8 | 16-cell graph | |
9 | complete tripartite graph | |
10 | triangular graph | |
12 | complete bipartite graph | |
13 | 13-Paley graph | |
14 | crown graph | |
15 | generalized quadrangle | |
16 | rook graph | |
22 | (11,6,3)-Levi graph | |
27 | (3,3)-Hamming graph | |
32 | Kummer graph | |
36 | hexacode graph | |
= from | ||
42 | Hoffman-Singleton graph minus star | |
45 | halved Foster graph | |
52 | generalized hexagon | |
57 | Perkel graph | |
62 | (6,6)-cage graph | |
63 | first point graph of generalized hexagon and its dual | |
63 | second point graph of generalized hexagon and its dual | |
64 | hypercube graph | |
462 | odd graph | |
924 | bipartite Kneser graph | |
= bipartite double of the odd graph | ||
1456 | generalized dodecagon |
The connected distance-transitive graphs of order 7 are summarized by the following table (Brouwer et al. 1989, p. 223).
graph | intersection array | |
8 | complete graph | |
14 | complete bipartite graph | |
16 | crown graph | |
30 | (15,7,3)-Levi graph | |
50 | Hoffman-Singleton graph | |
64 | folded cube graph | |
98 | minus a parallel class | |
100 | bipartite double of the Hoffman-Singleton graph | |
128 | hypercube graph | |
310 | bipartite double of a Grassmann graph | |
330 | 2-residual of S(5,8,24) | |
= doubly truncated Witt graph | ||
990 | Ivanov-Ivanov-Faradjev graph | |
1716 | odd graph | |
3432 | bipartite Kneser graph | |
= bipartite double of the odd graph |
The connected distance-transitive graphs of order 8 are summarized by the following table (Brouwer et al. 1989, pp. 223-224).
graph | intersection array | |
9 | complete graph | |
10 | cocktail party graph | |
12 | complete tripartite graph | |
15 | triangular graph | |
16 | complete bipartite graph | |
17 | 17-Paley graph | |
18 | crown graph | |
25 | rook graph | |
27 | generalized quadrangle | |
30 | Levi graph of 2-(15,8,4) design | |
32 | (8,1)-Hadamard graph | |
64 | from | |
81 | (4,3)-Hamming graph | |
105 | generalized hexagon | |
114 | (8,6)-cage graph | |
128 | folded cube graph | |
128 | minus a parallel class | |
256 | hypercube graph | |
425 | generalized octagon | |
6435 | odd graph | |
12870 | bipartite Kneser graph | |
= bipartite double of the odd graph |
The connected distance-transitive graphs of order 9 are summarized by the following table (Brouwer et al. 1989, p. 224).
graph | intersection array | |
10 | complete graph | |
12 | complete 4-partite graph | |
16 | rook complement graph | |
18 | complete bipartite graph | |
20 | crown graph | |
20 | tetrahedral Johnson graph | |
26 | (13,9,6)-Levi graph | |
= (13,9,6)-difference set Levi graph | ||
54 | from | |
= Levi graph of symmetric transversal design | ||
64 | (3,4)-Hamming graph | |
146 | (9,6)-cage | |
162 | minus a parallel class | |
256 | folded cube graph | |
280 | unitals in | |
1170 | (9,8)-cage | |
24310 | odd graph | |
48620 | bipartite Kneser graph | |
= bipartite double of the odd graph |
The connected distance-transitive graphs of order 10 are summarized by the following table (Brouwer et al. 1989, p. 224).
graph | intersection array | |
11 | complete graph | |
12 | cocktail party graph | |
15 | complete tripartite graph | |
16 | halved cube graph | |
20 | complete bipartite graph | |
21 | Kneser graph | |
21 | triangular graph | |
22 | crown graph | |
27 | generalized quadrangle | |
32 | first Levi graph of 2-(16,10,6) designs | |
= distance-3 graph of folded cube graph | ||
36 | rook graph | |
56 | Gewirtz graph | |
63 | Conway-Smith graph | |
65 | Hall graph | |
112 | bipartite double of the Gewirtz graph | |
182 | (10,6)-cage graph | |
186 | generalized hexagon | |
243 | (5,3)-Hamming graph | |
315 | Hall-Janko near octagon | |
512 | folded cube graph | |
1755 | generalized octagon | |
92378 | odd graph | |
132860 | generalized dodecagon | |
184756 | bipartite Kneser graph | |
= bipartite double of the odd graph |
The connected distance-transitive graphs of order 11 are summarized by the following table (Brouwer et al. 1989, p. 224).
graph | intersection array | |
12 | complete graph | |
22 | complete bipartite graph | |
24 | crown graph | |
242 | minus a parallel class | |
266 | Livingstone graph | |
352716 | odd graph | |
705432 | bipartite Kneser graph | |
= bipartite double of the odd graph |
The connected distance-transitive graphs of order 12 are summarized by the following table (Brouwer et al. 1989, pp. 224-225).
graph | intersection array | |
13 | complete graph | |
14 | cocktail party graph | |
15 | complete 5-partite graph | |
16 | complete 4-partite graph | |
18 | complete tripartite graph | |
24 | complete bipartite graph | |
25 | 25-Paley graph | |
26 | crown graph | |
28 | triangular graph | |
35 | tetrahedral Johnson graph | |
40 | first point graph of generalized quadrangle and its dual | |
40 | second point graph of generalized quadrangle and its dual | |
45 | point graph of generalized quadrangle | |
48 | (12,1)-Hadamard graph | |
49 | rook graph | |
68 | Doro graph | |
= | ||
125 | (3,5)-Hamming graph | |
175 | line graph of the Hoffman-Singleton graph | |
208 | on nonisotropic points | |
256 | (4,4)-Hamming graph | |
266 | generalized hexagon | |
364 | point graph of the generalized hexagon and its dual | |
729 | (6,3)-Hamming graph | |
2925 | generalized octagon | |
1352078 | odd graph | |
2704156 | bipartite Kneser graph | |
= bipartite double of the odd graph |
The connected distance-transitive graphs of order 13 are summarized by the following table (Brouwer et al. 1989, p. 225).
graph | intersection array | |
14 | complete graph | |
26 | complete bipartite graph | |
28 | crown graph | |
28 | 28-Taylor graph | |
80 | (40,13,4)-Levi graph | |
338 | minus a parallel class | |
2420 | doubled Grassmann graph | |
5200300 | odd graph | |
10400600 | bipartite Kneser graph | |
= bipartite double of the odd graph |