Degree diameter problem

Unsolved problem in mathematics

Given positive integers d and k, what is the maximum possible number of vertices in a finite simple graph of maximum degree at most d and diameter at most k?

More unsolved problems in mathematics

The Moore bound is attained by the complete graph $K_{d+1}$ when $k=1$ and by the odd cycle $C_{2k+1}$ when $d=2$.

In graph theory, the degree–diameter problem asks for the maximum possible number $n_{d,k}$ of vertices in a finite simple undirected graph of maximum degree at most $d$ and diameter at most $k$. 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. The exact value of $n_{d,k}$ is unknown for most pairs $(d,k)$.

A 2026 preprint by Wouter Cames van Batenburg and Samuel Korsky reports a proof that, for every fixed positive integer $k$,

$\lim _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1.$

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.