In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a distance-transitive graph is a
graph such that, given any two
vertices and at any
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects, points, people, or ideas are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two co ...
, and any other two vertices and at the same distance, there is an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphism ...
of the graph that carries to and to . Distance-transitive graphs were first defined in 1971 by
Norman L. Biggs and D. H. Smith.
A distance-transitive graph is interesting partly because it has a large
automorphism group. Some interesting
finite group
In abstract algebra, a finite group is a group whose underlying set is finite. Finite groups often arise when considering symmetry of mathematical or physical objects, when those objects admit just a finite number of structure-preserving tra ...
s are the automorphism groups of distance-transitive graphs, especially of those whose
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...
is 2.
Examples
Some first examples of families of distance-transitive graphs include:
* The
Johnson graphs.
* The
Grassmann graphs.
* The
Hamming Graphs (including
Hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cubical graph, cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has ...
s).
* The
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
The folded cube graph of dimension ''k'' (containin ...
s.
* The square
rook's graphs.
* The
Livingstone graph.
Classification of cubic distance-transitive graphs
After introducing them in 1971,
Biggs
Biggs may refer to:
Arts and entertainment
* Biggs (TV channel), a Portuguese television channel formerly for kids, teens and youth and now for teens and youth.
* Biggs Darklighter, a character in ''Star Wars Episode IV: A New Hope''
* Biggs, a re ...
and Smith showed that there are only 12 finite connected
trivalent distance-transitive graphs. These are:
Relation to distance-regular graphs
Every distance-transitive graph is
distance-regular, but the converse is not necessarily true.
In 1969, before publication of the Biggs–Smith definition, a Russian group led by
Georgy Adelson-Velsky showed that there exist graphs that are distance-regular but not distance-transitive. The smallest distance-regular graph that is not distance-transitive is the
Shrikhande graph, with 16 vertices and degree 6. 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.
References
;Early works
*.
*.
*.
*.
*.
;Surveys
*, chapter 20.
*.
*, chapter 7.
*.
*, section 4.5.
*.
External links
*{{mathworld, title=Distance-Transitive Graph, urlname=Distance-TransitiveGraph
Algebraic graph theory
Graph families
Regular graphs