Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Distance-regular graph
Summary
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.
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.
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.
Suppose is a connected distance-regular graph of valency with intersection array . For all : let denote the -regular graph with adjacency matrix 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 .
for all .
and .
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 .
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.