Distance-regular graph

From Quire, the open reference·Graph property·2 min read

Graph families defined by their automorphisms
distance-transitive · → · distance-regular · ← · strongly regular
↓
symmetric (arc-transitive) · ← · t-transitive, t ≥ 2 · skew-symmetric
↓
_{(if connected)} vertex- and edge-transitive · → · edge-transitive and regular · → · edge-transitive
↓ · ↓ · ↓
vertex-transitive · → · regular · → · _{(if bipartite)} biregular
↑
Cayley graph · ← · zero-symmetric · asymmetric

In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and w.

Some authors exclude the complete graphs and disconnected graphs from this definition.

Every distance-transitive graph 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.

Intersection arrays#edit

The intersection array of a distance-regular graph is the array ${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$ in which ${\displaystyle d}$ is the diameter of the graph and for each ${\displaystyle 1\leq j\leq d}$ , ${\displaystyle b_{j$ gives the number of neighbours of ${\displaystyle u}$ at distance ${\displaystyle j+1}$ from ${\displaystyle v}$ and ${\displaystyle c_{j$ gives the number of neighbours of ${\displaystyle u}$ at distance ${\displaystyle j-1}$ from ${\displaystyle v}$ for any pair of vertices ${\displaystyle u}$ and ${\displaystyle v}$ at distance ${\displaystyle j}$ . There is also the number ${\displaystyle a_{j$ that gives the number of neighbours of ${\displaystyle u}$ at distance ${\displaystyle j}$ from ${\displaystyle v}$ . The numbers ${\displaystyle a_{j},b_{j},c_{j$ are called the intersection numbers of the graph. They satisfy the equation ${\displaystyle a_{j}+b_{j}+c_{j}=k,}$ where ${\displaystyle k=b_{0$ is the valency, i.e., the number of neighbours, of any vertex.

It turns out that a graph ${\displaystyle G}$ of diameter ${\displaystyle d}$ is distance regular if and only if it has an intersection array in the preceding sense.

Cospectral and disconnected distance-regular graphs#edit

A pair of connected distance-regular graphs are cospectral if their adjacency matrices have the same spectrum. 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 of cospectral distance-regular graphs.

Properties#edit

Suppose ${\displaystyle G}$ is a connected distance-regular graph of valency ${\displaystyle k}$ with intersection array ${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$ . For each ${\displaystyle 0\leq j\leq d,}$ let ${\displaystyle k_{j$ denote the number of vertices at distance ${\displaystyle j}$ from any given vertex and let ${\displaystyle G_{j$ denote the ${\displaystyle k_{j$ -regular graph with adjacency matrix ${\displaystyle A_{j$ formed by relating pairs of vertices on ${\displaystyle G}$ at distance ${\displaystyle j}$ .

Graph-theoretic properties#edit

${\displaystyle {\frac {k_{j+1{k_{j={\frac {b_{j{c_{j+1$ for all ${\displaystyle 0\leq j<d}$ .
${\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}$ and ${\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0$ .

Spectral properties#edit

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

If ${\displaystyle G}$ is strongly regular, then ${\displaystyle n\leq 4m-1}$ and ${\displaystyle k\leq 2m-1}$ .

Association scheme#edit

The ${\displaystyle i}$ -distance adjacency matrices ${\displaystyle A_{i$ for ${\displaystyle i=0,1,...,d}$ of a distance-regular graph form an association scheme.

Examples#edit

The degree 7 Klein graph and associated map embedded in an orientable surface of genus 3. This graph is distance regular with intersection array {7,4,1;1,2,7} and automorphism group PGL(2,7). Image: source and license

Some first examples of distance-regular graphs include:

The complete graphs.
The cycle graphs.
The odd graphs.
The Moore graphs.
The collinearity graph of a regular near polygon.
The Wells graph and the Sylvester graph.
Strongly regular graphs are the distance-regular graphs of diameter 2.

Classification of distance-regular graphs#edit

There are only finitely many distinct connected distance-regular graphs of any given valency ${\displaystyle k>2}$ .^[1]

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity ${\displaystyle m>2}$ ^[2] (with the exception of the complete multipartite graphs).

Cubic distance-regular graphs#edit

The cubic distance-regular graphs have been completely classified.

The 13 distinct cubic distance-regular graphs are K₄ (or Tetrahedral graph), K_3,3, the Petersen graph, the Cubical graph, the Heawood graph, the Pappus graph, the Coxeter graph, the Tutte–Coxeter graph, the Dodecahedral graph, the Desargues graph, Tutte 12-cage, the Biggs–Smith graph, and the Foster graph.

References#edit

^ Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. (2015-01-10). "There are only finitely many distance-regular graphs of fixed valency greater than two". Advances in Mathematics. 269 (Supplement C): 1–55. arXiv:0909.5253. doi:10.1016/j.aim.2014.09.025. S2CID 18869283.
^ Godsil, C. D. (1988-12-01). "Bounding the diameter of distance-regular graphs". Combinatorica. 8 (4): 333–343. doi:10.1007/BF02189090. ISSN 0209-9683. S2CID 206813795.