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 conne ...
, a distance-regular graph is a
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...
such that for any two
vertices and , the number of vertices at
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"). ...
from and at distance from depends only upon , , and the distance between and .
Every
distance-transitive graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carrie ...
is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having 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 ...
.
Intersection arrays
It turns out that a graph
of diameter
is distance-regular if and only if there is an array of integers
such that for all
,
gives the number of neighbours of
at distance
from
and
gives the number of neighbours of
at distance
from
for any pair of vertices
and
at distance
on
. The array of integers characterizing a distance-regular graph is known as its intersection array.
Cospectral distance-regular graphs
A pair of connected distance-regular graphs are
cospectral if and only if they have the same intersection array.
A distance-regular graph is disconnected if and only if it is a
disjoint union
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
of cospectral distance-regular graphs.
Properties
Suppose
is a connected distance-regular graph of
valency with intersection array
. For all
: let
denote the
-regular graph with
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
formed by relating pairs of vertices on
at distance
, and let
denote the number of neighbours of
at distance
from
for any pair of vertices
and
at distance
on
.
Graph-theoretic properties
*
for all
.
*
and
.
Spectral properties
*
for any eigenvalue multiplicity
of
, unless
is a complete multipartite graph.
*
for any eigenvalue multiplicity
of
, unless
is a cycle graph or a complete multipartite graph.
*
if
is a simple eigenvalue of
.
*
has
distinct eigenvalues.
If
is
strongly regular, then
and
.
Examples
Some first examples of distance-regular graphs include:
* The
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. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
s.
* The
cycles graphs.
* The
odd graph
In the mathematical field of graph theory, the odd graphs ''On'' are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.
Definition and examples
The odd graph ''On'' ...
s.
* The
Moore graph
In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must e ...
s.
* The collinearity graph of a
regular near polygon.
* The
Wells graph and the
Sylvester graph.
*
* Strongly regular graphs of diameter
.
Classification of distance-regular graphs
There are only finitely many distinct connected distance-regular graphs of any given valency
.
Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity
(with the exception of the complete multipartite graphs).
Cubic distance-regular graphs
The
cubic distance-regular graphs have been completely classified.
The 13 distinct cubic distance-regular graphs are
K4 (or
Tetrahedral graph
In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...
),
K3,3, the
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 n ...
, the
Cubical graph
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the only r ...
, the
Heawood graph Heawood is a surname. Notable people with the surname include:
*Jonathan Heawood, British journalist
*Percy John Heawood (1861–1955), British mathematician
**Heawood conjecture
**Heawood graph
**Heawood number In mathematics, the Heawood number ...
, the
Pappus graph
In the mathematical field of graph theory, the Pappus graph is a bipartite 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 ...
, the
Coxeter graph
In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.
Properties
The Coxeter ...
, the
Tutte–Coxeter graph
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. ...
, the
Dodecahedral graph
A regular dodecahedron or pentagonal dodecahedron is a dodecahedron that is regular, which is composed of 12 regular pentagonal faces, three meeting at each vertex. It is one of the five Platonic solids. It has 12 faces, 20 vertices, 30 edges ...
, the
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 Girard Desargues, arises from several different combinatorial constructions, has a high level ...
,
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. ...
, the
Biggs–Smith graph
In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.
It has chromatic number 3, chromatic index 3, radius 7, diameter 7 and girth 9. It is also a 3- vertex-connected graph a ...
, and the
Foster graph
In the mathematical field of graph theory, the Foster graph is a bipartite 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 ...
.
References
Further reading
*
{{DEFAULTSORT:Distance-Regular Graph
Algebraic graph theory
Graph families
Regular graphs