Degree diameter problem

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. n_{d,k}=\max\bigl\{|V(G)|:\Delta(G)\leq d,\ \operatorname{diam}(G)\leq k\bigr\}, where \Delta(G) denotes the maximum degree of G . The elementary cases are n_{d,1}=d+1,\qquad n_{1,k}=2,\qquad n_{2,k}=2k+1. They are attained by complete graphs, a single edge, and odd cycles, respectively. To obtain an upper bound, fix a vertex v . There are at most d vertices at distance one from v , and at most d(d-1)^{i-1} vertices at distance i , since each vertex other than v has at most d-1 edges leading farther away from v . Consequently, n_{d,k}\leq M_{d,k}=1+d\sum_{i=0}^{k-1}(d-1)^i, where M_{d,k} is the Moore bound. Equivalently, M_{d,k}= \begin{cases} 1+d\displaystyle\frac{(d-1)^k-1}{d-2},&d\geq3,\\[6pt] 2k+1,&d=2,\\ 2,&d=1. \end{cases} For every fixed k , M_{d,k}=d^k+O_k(d^{k-1}) as d\to\infty . \delta(G)=M_{d,k}-|V(G)| is called its defect. Moore graphs have defect zero. Graphs of small positive defect are studied as finite approximations to Moore graphs. For d=2 , the exact value is n_{2,k}=2k+1 . For every fixed d\geq3 , Bollobás and Fernandez de la Vega showed that almost every d -regular graph on n vertices has diameter (1+o(1))\log_{d-1}n as n\to\infty . Together with the Moore bound, this gives n_{d,k}=(d-1)^{k+o(k)} as k\to\infty for each fixed d\geq3 . Thus random regular graphs provide constructions with the optimal exponential growth rate. This result does not determine the asymptotic ratio n_{d,k}/M_{d,k} . \mu_k=\liminf_{d\to\infty}\frac{n_{d,k}}{d^k}. The 2013 survey by Miller and Širáň recorded that \mu_1=\mu_2=\mu_3=\mu_5=1 and that \mu_4\geq\frac14. For every fixed k\geq2 , Bollobás conjectured that \limsup_{d\to\infty}\frac{n_{d,k}}{d^k}=1. 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 \lim_{d\to\infty}\frac{n_{d,k}}{d^k}=1 for every fixed positive integer k . Equivalently, \mu_k=1 and \lim_{d\to\infty}\frac{n_{d,k}}{M_{d,k}}=1 for every fixed k . 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. M^{\rightarrow}_{d,k}=1+d+d^2+\cdots+d^k = \begin{cases} \displaystyle\frac{d^{k+1}-1}{d-1},&d>1,\\[6pt] k+1,&d=1. \end{cases} A digraph attaining the bound is called a Moore digraph. Moore digraphs exist only in the elementary cases d=1 , represented by directed cycles, and k=1 , 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375259210 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.