HOME

TheInfoList



OR:

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-regular graph is a
regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...
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, 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 ...
from and at distance from depends only upon , , and the distance between and . Some authors exclude the complete graphs and disconnected graphs from this definition. 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 carri ...
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

The intersection array of a distance-regular graph is the array ( b_0, b_1, \ldots, b_; c_1, \ldots, c_d ) in which d is the diameter of the graph and for each 1 \leq j \leq d , b_j gives the number of neighbours of u at distance j+1 from v and c_j gives the number of neighbours of u at distance j - 1 from v for any pair of vertices u and v at distance j . There is also the number a_j that gives the number of neighbours of u at distance j from v . The numbers a_j, b_j, c_j are called the intersection numbers of the graph. They satisfy the equation a_j + b_j + c_j = k, where k = b_0 is the valency, i.e., the number of neighbours, of any vertex. It turns out that a graph G of diameter d is distance regular if and only if it has an intersection array in the preceding sense.


Cospectral and disconnected distance-regular graphs

A pair of connected distance-regular graphs are cospectral if their adjacency matrices have the same
spectrum A spectrum (: spectra or spectrums) is a set of related ideas, objects, or properties whose features overlap such that they blend to form a continuum. The word ''spectrum'' was first used scientifically in optics to describe the rainbow of co ...
. This is equivalent to their having the same intersection array. A distance-regular graph is disconnected if and only if it is a
disjoint union In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...
of cospectral distance-regular graphs.


Properties

Suppose G is a connected distance-regular graph of valency k with intersection array ( b_0, b_1, \ldots, b_; c_1, \ldots, c_d ) . For each 0 \leq j \leq d, let k_j denote the number of vertices at distance k from any given vertex and let G_ denote the k_ -regular graph with
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
A_j formed by relating pairs of vertices on G at distance j .


Graph-theoretic properties

* \frac = \frac for all 0 \leq j < d . * b_0 > b_1 \geq \cdots \geq b_ > 0 and 1 = c_1 \leq \cdots \leq c_d \leq b_0 .


Spectral properties

*G has d + 1 distinct eigenvalues. *The only simple eigenvalue of G is k, or both k and -k if G is bipartite. *k \leq \frac (m - 1)(m + 2) for any eigenvalue multiplicity m > 1 of G, unless G is a complete multipartite graph. *d \leq 3m - 4 for any eigenvalue multiplicity m > 1 of G, unless G is a cycle graph or a complete multipartite graph. If G is strongly regular, then n \leq 4m - 1 and k \leq 2m - 1.


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 i ...
s. * The
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s. * The
odd graph In the mathematics, mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph. The odd graphs have high odd girth, meaning that they conta ...
s. * The Moore graphs. * The collinearity graph of a regular near polygon. * The Wells graph and the Sylvester graph. *
Strongly regular graphs In graph theory, a strongly regular graph (SRG) is a regular graph with vertices and Degree (graph theory), degree such that for some given integers \lambda, \mu \ge 0 * every two adjacent vertices have common neighbours, and * every two no ...
are the distance-regular graphs of diameter 2.


Classification of distance-regular graphs

There are only finitely many distinct connected distance-regular graphs of any given valency k > 2. Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity m > 2 (with the exception of the complete multipartite graphs).


Cubic distance-regular graphs

The
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
distance-regular graphs have been completely classified. The 13 distinct cubic distance-regular graphs are K4 (or Tetrahedral graph), 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 i ...
, the Cubical graph, the Heawood graph, 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 ...
, the Coxeter graph, the
Tutte–Coxeter graph In the mathematics, 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 (graph theory), girt ...
, the Dodecahedral graph, the Desargues graph,
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. It is named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)- cage . It was discovered by C. T. Benson in ...
, the Biggs–Smith graph, and the Foster graph.


References


Further reading

* {{DEFAULTSORT:Distance-Regular Graph Algebraic graph theory Graph families Regular graphs