Distance-transitive graph

In mathematics, 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 arc transitive 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 Biggs and D. H. Smith, who showed that there are only 12 finite trivalent distance-transitive graphs. These are

• the complete graph K₄,
• the complete bipartite graph K_3,3,
• the Petersen graph,
• the graph of the cube,
• the graph of the dodecahedron,
• the Heawood graph,
• the Pappus graph,
• the 28-vertex Coxeter graph,
• the Desargues graph,
• the Tutte–Coxeter graph,
• the Foster graph, and
• the 102-vertex Biggs–Smith graph.

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. 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.

Square rook's graphs provide examples of distance-transitive graphs of arbitrarily high degree.

References

Early works

• .
  • .
    • .

      | doi = 10.1112/blms/3.2.155}}.

      • .Surveys
        • , chapter 20.

          | doi = 10.1016/j.ejc.2005.04.014}}.

          • , chapter 7.
            • .
              • , section 4.5.
                • .

                  External links