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.

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.

Related publications (30)

Related people (7)

Related units (2)

Related concepts (15)

Related courses (1)

Related lectures (20)

MATH-335: Coxeter groups

Study groups generated by reflections

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph G = (V, E) is a permutation σ of the vertex set V, such that the pair of vertices (u, v) form an edge if and only if the pair (σ(u), σ(v)) also form an edge. That is, it is a graph isomorphism from G to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs.

Coxeter graph

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter. The Coxeter graph has chromatic number 3, chromatic index 3, radius 4, diameter 4 and girth 7. It is also a 3-vertex-connected graph and a 3-edge-connected graph. It has book thickness 3 and queue number 2. The Coxeter graph is hypohamiltonian: it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian.

Distance-transitive graph

In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y. Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith. A distance-transitive graph is interesting partly because it has a large automorphism group.

Eigenvalues and Sequences MATH-467: Probabilistic methods in combinatorics

Discusses finding d-regular graphs with specific eigenvalue properties and the existence of Ramasugan sequences for d-opt prime numbers.

Positive Definite Coxeter Graphs MATH-335: Coxeter groups

Explores the classification of positive definite connected Coxeter graphs through detailed calculations and proofs.

Coxeter Groups: Classification and Fundamental Regions MATH-335: Coxeter groups

Explores Coxeter groups classification, rotation orders, fundamental regions, and geometric equivalence.

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...

Ottawa2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...

EPFL2023

, ,

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022