Distance-transitive graph

From Wikipedia, the free encyclopedia

The Biggs-Smith graph, the largest 3-regular distance-transitive graph.

Graph families defined by their automorphisms
distance-transitive	$\rightarrow$	distance-regular	$\leftarrow$	strongly regular
$\downarrow$
symmetric (arc-transitive)	$\leftarrow$	t-transitive, t ≥ 2
$\downarrow$ _{(if connected)}
vertex- and edge-transitive	$\rightarrow$	edge-transitive and regular	$\rightarrow$	edge-transitive
$\downarrow$		$\downarrow$		$\downarrow$
vertex-transitive	$\rightarrow$	regular	$\rightarrow$	_{(if bipartite)} biregular
$\uparrow$
Cayley graph		skew-symmetric		asymmetric

In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y.

A distance transitive graph is vertex transitive and symmetric as well as distance regular.

A distance-transitive graph is interesting partly because it has a large automorphism group. Some interesting finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2.

Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith, who showed that there are only 12 finite trivalent distance-transitive graphs. These are:

Graph name	Vertex count	Diameter	Girth	Intersection array
complete graph K₄	4	1	3	{3;1}
complete bipartite graph K_3,3	6	2	4	{3,2;1,3}
Petersen graph	10	2	5	{3,2;1,1}
Graph of the cube	8	3	4	{3,2,1;1,2,3}
Heawood graph	14	3	6	{3,2,2;1,1,3}
Pappus graph	18	4	6	{3,2,2,1;1,1,2,3}
Coxeter graph	28	4	7	{3,2,2,1;1,1,1,2}
Tutte–Coxeter graph	30	4	8	{3,2,2,2;1,1,1,3}
Graph of the dodecahedron	20	5	5	{3,2,1,1,1;1,1,1,2,3}
Desargues graph	20	5	6	{3,2,2,1,1;1,1,2,2,3}
Biggs-Smith graph	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Foster graph	90	8	10	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}

Independently in 1969 a Russian group led by Georgy Adelson-Velsky showed that there exist graphs that are distance-regular but not distance-transitive. The only graph of this type with degree three is the 126-vertex Tutte 12-cage. The smallest distance-regular graph that is not distance-transitive is the Shrikhande graph. Complete lists of distance-transitive graphs are known for some degrees larger than three, but the classification of distance-transitive graphs with arbitrarily large vertex degree remains open.

The simplest asymptotic family of examples of distance-transitive graphs is the Hypercube graphs. Other families are the folded cube graphs and the square rook's graphs. All three of these families have arbitrarily high degree.

References

Early works

Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; Faradžev, I. A. (1969), "An example of a graph which has no transitive group of automorphisms", Doklady Akademii Nauk SSSR 185: 975–976, MR 0244107 .
Biggs, Norman (1971), "Intersection matrices for linear graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23, MR 0285421 .
Biggs, Norman (1971), Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series 6, London & New York: Cambridge University Press, MR 0327563 .
Biggs, N. L.; Smith, D. H. (1971), "On trivalent graphs", Bulletin of the London Mathematical Society 3 (2): 155–158, doi:10.1112/blms/3.2.155, MR 0286693 .
Smith, D. H. (1971), "Primitive and imprimitive graphs", The Quarterly Journal of Mathematics. Oxford. Second Series 22 (4): 551–557, doi:10.1093/qmath/22.4.551, MR 0327584 .

Surveys

Biggs, N. L. (1993), "Distance-Transitive Graphs", Algebraic Graph Theory (2nd ed.), Cambridge University Press, pp. 155–163 , chapter 20.
Van Bon, John (2007), "Finite primitive distance-transitive graphs", European Journal of Combinatorics 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014, MR 2287450 .
Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), "Distance-Transitive Graphs", Distance-Regular Graphs, New York: Springer-Verlag, pp. 214–234 , chapter 7.
Cohen, A. M. Cohen (2004), "Distance-transitive graphs", in Beineke, L. W.; Wilson, R. J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications 102, Cambridge University Press, pp. 222–249 .
Godsil, C.; Royle, G. (2001), "Distance-Transitive Graphs", Algebraic Graph Theory, New York: Springer-Verlag, pp. 66–69 , section 4.5.
Ivanov, A. A. (1992), "Distance-transitive graphs and their classification", in Faradžev, I. A.; Ivanov, A. A.; Klin, M. et al., The Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Series) 84, Dordrecht: Kluwer, pp. 283–378, MR 1321634 |displayeditors= suggested (help).

External links

Weisstein, Eric W., "Distance-Transitive Graph", MathWorld.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.