Ykhjuy

In mathematics, 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 i = d(v, w).

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

It turns out that a graph G{displaystyle G} of diameter d{displaystyle d} is distance-regular if and only if there is an array of integers {b0,b1,⋯,bd−1;c1,⋯,cd}{displaystyle {b_{0},b_{1},cdots ,b_{d-1};c_{1},cdots ,c_{d}}} such that for all 1≤j≤d{displaystyle 1leq jleq d}, bj{displaystyle b_{j}} gives the number of neighbours of u{displaystyle u} at distance j+1{displaystyle j+1} from v{displaystyle v} and cj{displaystyle c_{j}} gives the number of neighbours of u{displaystyle u} at distance j−1{displaystyle j-1} from v{displaystyle v} for any pair of vertices u{displaystyle u} and v{displaystyle v} at distance j{displaystyle j} on G{displaystyle G}. 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 of cospectral distance-regular graphs.

Properties

Suppose G{displaystyle G} is a connected distance-regular graph of valency k{displaystyle k} with intersection array {b0,b1,⋯,bd−1;c1,⋯,cd}{displaystyle {b_{0},b_{1},cdots ,b_{d-1};c_{1},cdots ,c_{d}}}. For all 0≤j≤d{displaystyle 0leq jleq d}: let Gj{displaystyle G_{j}} denote the kj{displaystyle k_{j}}-regular graph with adjacency matrix Aj{displaystyle A_{j}} formed by relating pairs of vertices on G{displaystyle G} at distance j{displaystyle j}, and let aj{displaystyle a_{j}} denote the number of neighbours of u{displaystyle u} at distance j{displaystyle j} from v{displaystyle v} for any pair of vertices u{displaystyle u} and v{displaystyle v} at distance j{displaystyle j} on G{displaystyle G}.

Graph-theoretic properties

• 
  kj+1kj=bjcj+1{displaystyle {frac {k_{j+1}}{k_{j}}}={frac {b_{j}}{c_{j+1}}}} for all 0≤j<d{displaystyle 0leq j<d}.


• 
  b0>b1≥⋯≥bd−1>0{displaystyle b_{0}>b_{1}geq cdots geq b_{d-1}>0} and 1=c1≤⋯≤cd≤b0{displaystyle 1=c_{1}leq cdots leq c_{d}leq b_{0}}.

Spectral properties

• 
  k≤12(m−1)(m+2){displaystyle kleq {frac {1}{2}}(m-1)(m+2)} for any eigenvalue multiplicity m>1{displaystyle m>1} of G{displaystyle G}, unless G{displaystyle G} is a complete multipartite graph.


• 
  d≤3m−4{displaystyle dleq 3m-4} for any eigenvalue multiplicity m>1{displaystyle m>1} of G{displaystyle G}, unless G{displaystyle G} is a cycle graph or a complete multipartite graph.


• 
  λ∈{±k}{displaystyle lambda in {pm k}} if λ{displaystyle lambda } is a simple eigenvalue of G{displaystyle G}.


• 
  G{displaystyle G} has d+1{displaystyle d+1} distinct eigenvalues.

If G{displaystyle G} is strongly regular, then n≤4m−1{displaystyle nleq 4m-1} and k≤2m−1{displaystyle kleq 2m-1}.

Examples

Some first examples of distance-regular graphs include:

• The complete graphs.


• The cycles 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 of diameter 2{displaystyle 2}.

Classification of distance-regular graphs

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

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity m>2{displaystyle m>2}^[2] (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 K₄ (or tetrahedron), K_3,3, the Petersen graph, the cube, the Heawood graph, the Pappus graph, the Coxeter graph, the Tutte–Coxeter graph, the dodecahedron, the Desargues graph, Tutte 12-cage, the Biggs–Smith graph, and the Foster graph.

References

Further reading

• 
  Godsil, C. D. (1993). Algebraic combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. pp. xvi+362. ISBN 0-412-04131-6. MR 1220704.