In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a distance-transitive graph is a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 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

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....

 of the graph that carries v to x and w to y.

A distance transitive graph is vertex transitive

Vertex-transitive graph

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...

 and symmetric

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...

 as well as distance regular

Distance-regular graph

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance-regular...

.

A distance-transitive graph is interesting partly because it has a large automorphism group. Some interesting finite group

Finite group

In mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...

s 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

Norman L. Biggs

Norman Linstead Biggs is a mathematician focusing on discrete mathematics and in particular algebraic combinatorics, and his interests include computational learning theory, history of mathematics and historical metrology. As of 2006 he is Emeritus Professor at The London School of...

 and D. H. Smith, who showed that there are only 12 finite trivalent

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

 distance-transitive graphs. These are:

Graph name	Vertex count	Diameter Diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints are on the circle. The diameters are the longest chords of the circle...	Girth	Intersection array Intersection array In the mathematical field of graph theory, given a distance-regular graph G of diameter d, by definition there are integers bi and ci such that given any two vertices x and y in G at distance i, y has bi neighbours at distance i + 1 from x and ci neighbours at distance...
complete graph Complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...  K4	4	1	3	{3;1}
complete bipartite graph Complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...  K3,3	6	2	4	{3,2;1,3}
Petersen graph Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...	10	2	5	{3,2;1,1}
Graph of the cube Cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and...	8	3	4	{3,2,1;1,2,3}
Heawood graph Heawood graph In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.-Combinatorial properties:...	14	3	6	{3,2,2;1,1,3}
Pappus graph Pappus graph In the mathematical field of graph theory, the Pappus graph is a 3-regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon...	18	4	6	{3,2,2,1;1,1,2,3}
Coxeter graph Coxeter graph In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. All the cubic distance-regular graphs are known. The Coxeter graph is one of the 13 such graphs....	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 Desargues graph In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Gérard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial...	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 Foster graph In the mathematical field of graph theory, the Foster graph is a 3-regular graph with 90 vertices and 135 edges.The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is also a 3-vertex-connected and 3-edge-connected graph.All the cubic...	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

Georgy Adelson-Velsky

Georgy Maximovich Adelson-Velsky , is a Soviet mathematician and computer scientist. Along with E.M. Landis, he invented the AVL tree in 1962....

 showed that there exist graphs that are distance-regular

Distance-regular graph

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance-regular...

 but not distance-transitive. The only graph of this type with degree three is the 126-vertex Tutte 12-cage

Tutte 12-cage

In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte....

. The smallest distance-regular graph that is not distance-transitive is the Shrikhande graph

Shrikhande graph

In the mathematical field of graph theory, the Shrikhande graph is a named graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having a degree of 6.-Properties:...

. 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

Asymptotic analysis

In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...

 family of examples of distance-transitive graphs is the Hypercube graphs. Other families are the folded cube graph

Folded cube graph

In graph theory, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects opposite pairs of hypercube vertices.-Construction:...

s and the square rook's graph

Rook's graph

In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move...

s. All three of these families have arbitrarily high degree.