TOPICS
Search

Distance-Transitive Graph


A graph G 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 >2 (Brouwer et al. 1989, pp. 214 and 220). Furthermore, all distance-transitive graphs with vertex degree <=13 are known (Brouwer et al. 1989, pp. 221-225), as listed in the following tables.

The numbers of distance-transitive graphs on n=1, 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 n=9. The smallest graph that is symmetric but not distance-transitive is the circulant graph Ci_10(1,4).

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 H(2n-1,n-1) (i.e., bipartite doubles of the odd graphs O_n),

2. cocktail party graphs K_(n×2) ,

3. complete bipartite graphs K_(n,n),

4. complete graphs K_n,

5. complete k-partite graphs K_(m×n),

6. crown graphs K_2 square K_n^_,

7. empty graphs K^__n,

8. folded cube graphs  square _n,

9. Grassmann graphs J_q(n,k),

10. halved cube graphs Q_n/2,

11. hypercube graphs Q_n,

12. Johnson graphs J(n,k),

13. ladder rung graphs nP_2,

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

15. Paley graphs,

16. rook graphs K_n square K_n,

17. rook complement graphs K_n square K_n^_,

18. tetrahedral Johnson graphs J(n,3), and

19. triangular graphs L(K_n).

Distance-TransitiveGraph3

The connected distance-transitive graphs or order three are summarized by the following table.

Distance-TransitiveGraph4

The connected distance-transitive graphs of order 4 are summarized by the following table (Brouwer et al. 1989, p. 222).

Distance-TransitiveGraph6

The connected distance-transitive graphs of order 6 are summarized by the following table (Brouwer et al. 1989, p. 223).

Distance-TransitiveGraph7

The connected distance-transitive graphs of order 7 are summarized by the following table (Brouwer et al. 1989, p. 223).

Distance-TransitiveGraph8

The connected distance-transitive graphs of order 8 are summarized by the following table (Brouwer et al. 1989, pp. 223-224).

Distance-TransitiveGraph9

The connected distance-transitive graphs of order 9 are summarized by the following table (Brouwer et al. 1989, p. 224).

ngraphintersection array
10complete graph K_(10){9;1}
12complete 4-partite graph K_(4×3){9,2;1,9}
16rook complement graph K_4 square K_4^_{9,4;1,6}
18complete bipartite graph K_(9,9){9,8;1,9}
20crown graph K_2 square K_(10)^_{9,8,1;1,8,9}
20tetrahedral Johnson graph L(K_6){9,4,1;1,4,9}
26(13,9,6)-Levi graph{9,8,3;1,6,9}
= (13,9,6)-difference set Levi graph
543·K_(9,9) from RT[9,3;3]{9,8,6,1;1,3,8,9}
= Levi graph of symmetric transversal design STD_2[9,3]
64(3,4)-Hamming graph{9,6,3;1,2,3}
146(9,6)-cage{9,8,8;1,1,9}
162AG(2,9) minus a parallel class{9,8,8,1;1,1,8,9}
256folded cube graph  square _9{9,8,7,6;1,2,3,4}
280unitals in PG(2,4){9,8,6,3;1,1,3,8}
1170(9,8)-cage{9,8,8,8;1,1,1,9}
24310odd graph O_9{8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
48620bipartite Kneser graph H(17,9)
= bipartite double of the odd graph O_9
Distance-TransitiveGraph10

The connected distance-transitive graphs of order 10 are summarized by the following table (Brouwer et al. 1989, p. 224).

Distance-TransitiveGraph11

The connected distance-transitive graphs of order 11 are summarized by the following table (Brouwer et al. 1989, p. 224).

Distance-TransitiveGraph12

The connected distance-transitive graphs of order 12 are summarized by the following table (Brouwer et al. 1989, pp. 224-225).

Distance-TransitiveGraph13

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

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

Subject classifications