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

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

. Some interesting

finite group Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or ma ...

s 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 graph Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J(n,k) are the k-element subsets of an n-element set; two vertices are adjacent when the intersection of the two vertices (subs ...

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

s. * The Hamming Graphs. * 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'' (containing ...

s. * The square

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 of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...

s. * 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 an ...

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 Georgy Maximovich Adelson-Velsky (russian: Гео́ргий Макси́мович Адельсо́н-Ве́льский; name is sometimes transliterated as Georgii Adelson-Velskii) (8 January 1922 – 26 April 2014) was a Soviet and Israeli m ...

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 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 degree 6. Every pair of nodes h ...

, with 16 vertices and degree 6. The only graph of this type with degree three is the 126-vertex

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 Tutte 12-cage is the unique (3-12)- cage . It was discovered by C. T. Benson in 1966. ...

. 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