Distance-regular graph

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.