In graph theory, the degree–diameter problem of vertices in a finite simple undirected graph of maximum degree and diameter. A breadth-first search gives a general upper bound known as the Moore bound.

Exact equality in the Moore bound is exceptional. Apart from complete graphs, odd cycles, and the degree-one cases, the only known graphs attaining it are the Petersen graph and the Hoffman–Singleton graph; the only unresolved nontrivial parameter pair for equality is degree 57 and diameter 2..

,

This resolves a conjecture of Béla Bollobás and shows that, for every fixed diameter, the Moore bound is asymptotically tight as the degree tends to infinity.

History and motivation

A principal motivation for the degree–diameter problem is the design of communication and computer interconnection networks. In this interpretation, vertices represent processors or other devices, maximum degree limits the number of direct connections available at a vertex, and diameter bounds the largest number of links that must be traversed between two vertices.

An early treatment connected with this application was given by Bernard Elspas in a 1964 paper on interconnection-limited logic.

Definition and Moore bound

, define

. The elementary cases are

They are attained by complete graphs, a single edge, and odd cycles, respectively.

. Consequently,

is the Moore bound. Equivalently,

,

.

Moore graphs and defect

A graph attaining equality in the Moore bound is called a Moore graph. Any graph attaining the bound is necessarily regular.

are Moore graphs of degree two. For diameter two and degree greater than two, Hoffman and Singleton showed that the only possible degrees are 3, 7, and 57. The Petersen graph and the Hoffman–Singleton graph realize degrees 3 and 7, respectively, while the existence of a Moore graph of degree 57 remains open. Damerell and, independently, Bannai and Ito proved that there are no Moore graphs other than cycles with diameter at least three.

, the quantity

is called its defect. Moore graphs have defect zero. Graphs of small positive defect are studied as finite approximations to Moore graphs.

Bounds and constructions

.

Construction methods have used finite geometries, Cayley graphs and other vertex-transitive graphs, graph lifts and voltage assignments, graph products and compounding, computational search, and probabilistic methods. For most nontrivial parameter pairs, the largest known construction has not been proved optimal.

Asymptotic behaviour

Two principal asymptotic regimes arise according to whether the degree or the diameter is held fixed.

Fixed degree

vertices has diameter

.

Together with the Moore bound, this gives

.

Fixed diameter

, Delorme introduced the parameter

The 2013 survey by Miller and Širáň recorded that

and that

, Bollobás conjectured that

A stronger variant replaced the limit superior by the limit inferior. In their 2026 preprint, Wouter Cames van Batenburg and Samuel Korsky report a proof of the full limit

. Equivalently,

and

.

Their construction uses regular graphs whose vertices are partial flags in vector spaces over finite fields. The preprint is accompanied by a Lean 4 formalization of its central theorem chain, including the asymptotic theorem.

Relation to the degree–girth problem

The related degree–girth problem as a lower bound on its order. A graph attaining this lower bound is simultaneously a cage and a Moore graph.

For even girth, an analogous count leads to the bipartite Moore bound and the study of bipartite Moore graphs.

Directed and restricted variants

, the directed Moore bound is

, represented by complete digraphs.

Restricted forms of the degree–diameter problem have been studied for Cayley graphs, vertex-transitive graphs, bipartite graphs, planar graphs, graphs embeddable on a fixed surface, and several other graph classes.

Known values and open problems

are known for relatively few nontrivial parameter pairs. For most pairs, only upper bounds and the orders of the largest currently known constructions are available; these are recorded in the Table of the largest known graphs of a given diameter and maximal degree.

, and the regime in which both degree and diameter tend to infinity. In particular, it is unknown whether

tend to infinity, and whether the Moore gap

is unbounded.

See also

• Cage (graph theory)

• Table of the largest known graphs of a given diameter and maximal degree

• Table of vertex-symmetric degree–diameter digraphs

• Maximum degree-and-diameter-bounded subgraph problem

References