TOPICS
Search

Distance-Transitive Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A distance-transitive graph G is a graph whose automorphism group is transitive on pairs of vertices at each pairwise distance in the graph. For a connected graph, distance-transitivity is a strengthening 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 connected 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 number 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. balanced complete multipartite graphs K_(m×n),

6. crown graphs K_(n,n)-M,

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. halved folded cube graphs square _n/2,

12. hypercube graphs Q_n,

13. Johnson graphs J(n,k),

14. ladder rung graphs nP_2,

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

16. Paley graphs,

17. Peisert graphs,

18. rook graphs K_n square K_n,

19. rook complement graphs K_n square K_n^_,

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

21. triangular graphs L(K_n).

Distance-TransitiveGraph3

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

ngraphintersection array
4tetrahedral graph K_4{3;1}
6utility graph K_(3,3){3,2;1,3}
8cubical graph Q_3{3,2,1;1,2,3}
10Petersen graph P{3,2;1,1}
14Heawood graph{3,2,2;1,1,3}
18Pappus graph{3,2,2,1;1,1,2,3}
20Desargues graph{3,2,2,1,1;1,1,2,2,3}
20dodecahedral graph{3,2,1,1,1;1,1,1,2,3}
28Coxeter graph{3,2,2,1;1,1,1,2}
30Tutte 8-cage{3,2,2,2;1,1,1,3}
90Foster graph{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
102Biggs-Smith graph{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Distance-TransitiveGraph4

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

ngraphintersection array
5pentatope graph K_5{4;1}
6octahedral graph K_(3×2){4,1;1,4}
8complete bipartite graph K_(4,4){4,3;1,4}
9generalized quadrangle GQ(2,1){4,2;1,2}
10crown graph K_2 square K_5^_{4,3,1;1,3,4}
14distance 3 graph of Heawood graph{4,3,2;1,2,4}
= quartic vertex-transitive graph Qt31
= Levi graph of 2-(7,4,2) design
15Petersen line graph L(P){4,2,1;1,1,4}
16tesseract graph Q_4{4,3,2,1;1,2,3,4}
21line graph of Heawood graph{4,2,2;1,1,2}
= generalized hexagon GH(2,1)
26(4,6)-cage graph{4,3,3;1,1,4}
32AG(2,4) minus a parallel class{4,3,3,1;1,1,3,4}
35odd graph O_4{4,3,3;1,1,2}
45generalized octagon GO(2,1){4,2,2,2;1,1,1,2}
70bipartite Kneser graph H(7,3){4,3,3,2,2,1,1;1,1,2,2,3,3,4}
= bipartite double of the odd graph O_4
728generalized dodecagon GD(1,3){4,3,3,3,3,3;1,1,1,1,1,4}
Distance-TransitiveGraph5

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

ngraphintersection array
6complete graph K_6{5;1}
10complete bipartite graph K_(5,5){5,4;1,5}
12crown graph K_2 square K_6^_{5,4,1;1,4,5}
12icosahedral graph{5,2,1;1,2,5}
16Clebsch graph{5,4;1,2}
22Levi graph of 2-(11,5,2) design{5,4,3;1,2,5}
325-hypercube graph{5,4,3,2,1;1,2,3,4,5}
32Wells graph{5,4,1,1;1,1,4,5}
36Sylvester graph{5,4,2;1,1,4}
42(5,6)-cage graph{5,4,4;1,1,5}
= generalized hexagon GH(1,4)
50AG(2,5) minus a parallel class{5,4,4,1;1,1,4,5}
126odd graph O_5{5,4,4,3;1,1,2,2}
170(5,8)-cage graph{5,4,4,4;1,1,1,5}
= generalized octagon GO(1,4)
252bipartite Kneser graph H(9,4){5,4,4,3,3,2,2,1,1;1,1,2,2,3,3,4,4,5}
= bipartite double of the odd graph O_5
Distance-TransitiveGraph6

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

ngraphintersection array
7complete graph K_7{6;1}
816-cell graph K_(4×2){6,1;1,6}
9complete tripartite graph K_(3,3,3){6,2;1,6}
10triangular graph L(K_5){6,2;1,4}
12complete bipartite graph K_(6,6){6,5;1,6}
1313-Paley graph{6,3;1,3}
14crown graph K_2 square K_7^_{6,5,1;1,5,6}
15generalized quadrangle GQ(2,2){6,4;1,3}
16rook graph K_4 square K_4{6,3;1,2}
22(11,6,3)-Levi graph{6,5,3;1,3,6}
27(3,3)-Hamming graph{6,4,2;1,2,3}
32Kummer graph square _6{6,5,4;1,2,6}
36hexacode graph{6,5,4,1;1,2,5,6}
= 3·K_(6,6) from RT[6,2;3]
42Hoffman-Singleton graph minus star{6,5,1;1,1,6}
45halved Foster graph{6,4,2,1;1,1,4,6}
52generalized hexagon GH(3,1){6,3,3;1,1,2}
57Perkel graph{6,5,2;1,1,3}
62(6,6)-cage graph{6,5,5;1,1,6}
63first point graph of generalized hexagon GH(2,2) and its dual{6,4,4;1,1,3}
63second point graph of generalized hexagon GH(2,2) and its dual{6,4,4;1,1,3}
64hypercube graph Q_6{6,5,4,3,2,1;1,2,3,4,5,6}
462odd graph O_6{6,5,5,4,4;1,1,2,2,3}
924bipartite Kneser graph H(11,5){6,5,5,4,4,3,3,2,2,1,1;1,1,2,2,3,3,4,4,5,5,6}
= bipartite double of the odd graph O_6
1456generalized dodecagon GD(3,1){6,3,3,3,3,3;1,1,1,1,1,2}
Distance-TransitiveGraph7

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

ngraphintersection array
8complete graph K_8{7;1}
14complete bipartite graph K_(7,7){7,6;1,7}
16crown graph K_2 square K_8^_{7,6,1;1,6,7}
30(15,7,3)-Levi graph{7,6,4;1,3,7}
50Hoffman-Singleton graph{7,6;1,1}
64folded cube graph square _7{7,6,5;1,2,3}
98AG(2,7) minus a parallel class{7,6,6,1;1,1,6,7}
100bipartite double of the Hoffman-Singleton graph{7,6,6,1,1;1,1,6,6,7}
128hypercube graph Q_7{7,6,5,4,3,2,1;1,2,3,4,5,6,7}
310bipartite double of a Grassmann graph J_2(5,2){7,6,6,4,4;1,1,3,3,7}
3302-residual of S(5,8,24){7,6,4,4;1,1,1,6}
= doubly truncated Witt graph
990Ivanov-Ivanov-Faradjev graph{7,6,4,4,4,1,1,1;1,1,1,2,4,4,6,7}
1716odd graph O_7{7,6,6,5,5,4;1,1,2,2,3,3}
3432bipartite Kneser graph H(13,6){7,6,6,5,5,4,4,3,3,2,2,1,1;1,1,2,2,3,3,4,4,5,5,6,6,7}
= bipartite double of the odd graph O_7
Distance-TransitiveGraph8

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

ngraphintersection array
9complete graph K_9{8;1}
10cocktail party graph K_(5×2){8,1;1,8}
12complete tripartite graph K_(4,4,4){8,3;1,8}
15triangular graph L(K_6){8,3;1,4}
16complete bipartite graph K_(8,8){8,7;1,8}
1717-Paley graph{8,4;1,4}
18crown graph K_2 square K_9^_{8,7,1;1,7,8}
25rook graph K_5 square K_5{8,4;1,2}
27generalized quadrangle GQ(2,4){8,6,1;1,3,8}
30Levi graph of 2-(15,8,4) design{8,7,4;1,4,8}
32(8,1)-Hadamard graph{8,7,4,1;1,4,7,8}
644·K_(8,8) from RT[8,2;4]{8,7,6,1;1,2,7,8}
81(4,3)-Hamming graph{8,6,4,2;1,2,3,4}
105generalized hexagon GH(4,1){8,4,4;1,1,2}
114(8,6)-cage graph{8,7,7;1,1,8}
128folded cube graph square _8{8,7,6,5;1,2,3,8}
128AG(2,8) minus a parallel class{8,7,7,1;1,1,7,8}
256hypercube graph Q_8{8,7,6,5,4,3,2,1;1,2,3,4,5,6,7,8}
425generalized octagon GO(4,1){8,4,4,4;1,1,1,2}
6435odd graph O_8{8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
12870bipartite Kneser graph H(15,7)
= bipartite double of the odd graph O_8
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).

ngraphintersection array
11complete graph K_(11){10;1}
12cocktail party graph K_(6×2){10,1;1,10}
15complete tripartite graph K_(5,5,5){10,4;1,10}
16halved cube graph Q_5/2{10,3;1,6}
20complete bipartite graph K_(10,10){10,9;1,10}
21Kneser graph K(7,2){10,6;1,6}
21triangular graph L(K_7){10,4;1,4}
22crown graph K_2 square K_(11)^_{10,9,1;1,9,10}
27generalized quadrangle GQ(2,4){10,8;1,5}
32first Levi graph of 2-(16,10,6) designs{10,9,4;1,6,10}
= distance-3 graph of folded cube graph square _6
36rook graph K_6 square K_6{10,5;1,2}
56Gewirtz graph{10,9;1,2}
63Conway-Smith graph{10,6,4,1;1,2,6,10}
65Hall graph{10,6,4;1,2,5}
112bipartite double of the Gewirtz graph{10,9,8,2,1;1,2,8,9,10}
182(10,6)-cage graph{10,9,9;1,1,10}
186generalized hexagon GH(5,1){10,5,5;1,1,2}
243(5,3)-Hamming graph{10,8,6,4,2;1,2,3,4,5}
315Hall-Janko near octagon{10,8,8,2;1,1,4,5}
512folded cube graph square _(10){10,9,8,7,6;1,2,3,4,10}
1755generalized octagon GO(2,4){10,8,8,8;1,1,1,5}
92378odd graph O_(10){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
132860generalized dodecagon GD(1,9){10,9,9,9,9,9;1,1,1,1,1,10}
184756bipartite Kneser graph H(19,10)
= bipartite double of the odd graph O_(10)
Distance-TransitiveGraph11

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

ngraphintersection array
12complete graph K_(12){11;1}
22complete bipartite graph K_(11,11){11,10;1,11}
24crown graph K_2 square K_(12)^_{11,10,1;1,10,11}
242AG(2,11) minus a parallel class{11,10,10,1;1,1,10,11}
266Livingstone graph{11,10,6,1;1,1,5,11}
352716odd graph O_(11){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
705432bipartite Kneser graph H(21,11)
= bipartite double of the odd graph O_(11)
Distance-TransitiveGraph12

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

ngraphintersection array
13complete graph K_(13){12;1}
14cocktail party graph K_(7×2){12,1;1,12}
15complete 5-partite graph K_(5×3){12,2;1,12}
16complete 4-partite graph K_(4×4){12,3;1,12}
18complete tripartite graph K_(6,6,6){12,5;1,12}
24complete bipartite graph K_(12,12){12,11;1,12}
2525-Paley graph{12,6;1,6}
26crown graph K_2 square K_(13)^_{12,11,1;1,11,12}
28triangular graph L(K_8){12,5;1,4}
35tetrahedral Johnson graph J(3,7){12,6,2;1,4,9}
40first point graph of generalized quadrangle GQ(3,3) and its dual{12,9;1,4}
40second point graph of generalized quadrangle GQ(3,3) and its dual{12,9;1,4}
45point graph of generalized quadrangle GQ(4,2){12,8;1,3}
48(12,1)-Hadamard graph{12,11,6,1;1,6,11,12}
49rook graph K_7 square K_7{12,6;1,2}
68Doro graph{12,10,3;1,3,8}
= PSigmaL(2,16)
125(3,5)-Hamming graph{12,8,4;1,2,3}
175line graph of the Hoffman-Singleton graph{12,6,5;1,1,4}
208PGammaU(3,4) on nonisotropic points{12,10,5;1,1,8}
256(4,4)-Hamming graph{12,9,6,3;1,2,3,4}
266generalized hexagon GH(1,11){12,11,11;1,1,12}
364point graph of the generalized hexagon GH(3,3) and its dual{12,9,9;1,1,4}
729(6,3)-Hamming graph{12,10,8,6,4,2;1,2,3,4,5,6}
2925generalized octagon GO(4,2){12,8,8,8;1,1,1,3}
1352078odd graph O_(12){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
2704156bipartite Kneser graph H(23,11)
= bipartite double of the odd graph O_(12)
Distance-TransitiveGraph13

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

ngraphintersection array
14complete graph K_(14){13;1}
26complete bipartite graph K_(13,13){13,12;1,13}
28crown graph K_2 square K_(14)^_{13,12,1;1,12,13}
2828-Taylor graph{13,6,1;1,6,13}
80(40,13,4)-Levi graph{13,12,9;1,4,13}
338AG(2,13) minus a parallel class{13,12,12,1;1,1,12,13}
2420doubled Grassmann graph J_3(5,2){13,12,12,9,9;1,1,4,4,13}
5200300odd graph O_(13){8,7,7,6,6,5,5,4;1,1,2,2,3,3,4,4}
10400600bipartite Kneser graph H(25,12)
= bipartite double of the odd graph O_(13)

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. https://www.math.mun.ca/distanceregular/.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 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Distance-Transitive Graph

Cite this as:

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

Subject classifications