In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a distance-transitive graph is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
such that, given any two
vertices and at any
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
, and any other two vertices and at the same distance, there is an
automorphism of the graph that carries to and to . Distance-transitive graphs were first defined in 1971 by
Norman L. Biggs
Norman Linstead Biggs (born 2 January 1941) is a leading British mathematician focusing on discrete mathematics and in particular algebraic combinatorics..
Education
Biggs was educated at Harrow County Grammar School and then studied mathemat ...
and D. H. Smith.
A distance-transitive graph is interesting partly because it has a large
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is th ...
. Some interesting
finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2.
Examples
Some first examples of families of distance-transitive graphs include:
* The
Johnson graphs.
* The
Grassmann graph
In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph are the -dimensional subspaces of an -dimensional vector space over a finite field of order ; two ver ...
s.
* The
Hamming Graphs.
* The
folded cube graphs.
* The square
rook's graphs.
* The
hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, e ...
s.
* The
Livingstone graph.
Classification of cubic distance-transitive graphs
After introducing them in 1971,
Biggs and Smith showed that there are only 12 finite
trivalent
In chemistry, the valence (US spelling) or valency (British spelling) of an element is the measure of its combining capacity with other atoms when it forms chemical compounds or molecules.
Description
The combining capacity, or affinity of a ...
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