TOPICS

# Distance-Transitive Graph

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 ),

6. crown graphs ,

7. empty graphs ,

11. hypercube graphs ,

12. Johnson graphs ,

14. odd graphs (Brouwer et al. 1989, p. 222, Theorem 7.5.2),

15. Paley graphs,

16. rook graphs ,

18. tetrahedral Johnson graphs , and

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

Bipartite Double Graph, Conway-Smith Graph, Distance-Regular Graph, Global Parameters, Halved Graphs, Hypercube Graph, Intersection Array, Livingstone Graph, Local Graph, Odd Graph, Shrikhande Graph, Suzuki 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.Biggs, N. L. "Distance-Transitive Graphs." Ch. 20 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 155-163, 1993.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Distance-Transitive Graphs." Ch. 7 in Distance-Regular Graphs. New York: Springer-Verlag, pp. 214-234, 1989.DistanceRegular.org. http://www.distanceregular.org.Godsil, C. and Royle, G. "Distance-Transitive Graphs." §4.5 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 66-69, 2001.Sloane, N. J. A. Sequence A308601

## Referenced on Wolfram|Alpha

Distance-Transitive Graph

## Cite this as:

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