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. halved folded cube graphs 
,
12. hypercube graphs 
,
13. Johnson graphs 
,
14. ladder rung graphs 
,
15. odd graphs (Brouwer et al. 1989, p. 222, Theorem 7.5.2),
16. Paley graphs,
17. Peisert graphs,
18. rook graphs 
,
19. rook complement graphs 
,
20. tetrahedral Johnson graphs 
, and
21. 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).
The connected distance-transitive graphs of order 6 are summarized by the following table (Brouwer et al. 1989, p. 223).
The connected distance-transitive graphs of order 7 are summarized by the following table (Brouwer et al. 1989, p. 223).
The connected distance-transitive graphs of order 8 are summarized by the following table (Brouwer et al. 1989, pp. 223-224).
The connected distance-transitive graphs of order 9 are summarized by the following table (Brouwer et al. 1989, p. 224).
The connected distance-transitive graphs of order 10 are summarized by the following table (Brouwer et al. 1989, p. 224).
The connected distance-transitive graphs of order 11 are summarized by the following table (Brouwer et al. 1989, p. 224).
The connected distance-transitive graphs of order 12 are summarized by the following table (Brouwer et al. 1989, pp. 224-225).
The connected distance-transitive graphs of order 13 are summarized by the following table (Brouwer et al. 1989, p. 225).
See also
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
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
Cite this as:
Weisstein, Eric W. "Distance-Transitive Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Distance-TransitiveGraph.html