Distance-transitive graph

Distance-transitive graph
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
vertex-transitive \rightarrow regular
\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 K4 4 1 3 {3;1}
complete bipartite graph K3,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, MR0244107 .
  • Biggs, Norman (1971), "Intersection matrices for linear graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23, MR0285421 .
  • Biggs, Norman (1971), Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series, 6, London & New York: Cambridge University Press, MR0327563 .
  • 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, MR0286693 .
  • 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, MR0327584 .
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, MR2287450 .
  • 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, MR1321634 .

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Distance-regular graph — Graph families defined by their automorphisms distance transitive distance regular strongly regular …   Wikipedia

  • Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph)[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original… …   Wikipedia

  • Vertex-transitive graph — In mathematics, a vertex transitive graph is a graph G such that, given any two vertices v1 and v2 of G , there is some automorphism : f : V(G) → V(G) such that : f (v1) = v2. In other words, a graph is vertex transitive if its automorphism group …   Wikipedia

  • Graph automorphism — In graph theoretical mathematics, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge vertex connectivity.Formally, an automorphism of a graph G = ( V , E ) is a permutation sigma;… …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Algebraic graph theory — is a branch of mathematics in which algebraic methods are applied to problems about graphs. In one sense, algebraic graph theory studies graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, the… …   Wikipedia

  • Foster graph — infobox graph name = Foster graph image caption = namesake = vertices = edges = chromatic number = chromatic index = In graph theory the Foster graph is a graph on 90 vertices and 135 arcs. It is the unique distance transitive graph with… …   Wikipedia

  • Odd graph — The Petersen graph as an odd graph O3 Vertices Edges …   Wikipedia

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia

  • Nauru graph — The Nauru graph is Hamiltonian. Vertices 24 Edges 36 Radius 4 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”