Degree diameter problem

☆ Save On Wikipedia ↗
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 {\displaystyle K_{d+1}} {\displaystyle K_{d+1}} when k = 1 {\displaystyle k=1} {\displaystyle k=1} and by the odd cycle C 2 k + 1 {\displaystyle C_{2k+1}} {\displaystyle C_{2k+1}} when d = 2 {\displaystyle d=2} {\displaystyle d=2}.

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

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

lim d → ∞ n d , k d k = 1. {\displaystyle \lim _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1.} {\displaystyle \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.[2]

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.[1]

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

Definition and Moore bound

For positive integers d {\displaystyle d} {\displaystyle d} and k {\displaystyle k} {\displaystyle k}, define

n d , k = max { | V ( G ) | : Δ ( G ) ≤ d ,   diam ⁡ ( G ) ≤ k } , {\displaystyle n_{d,k}=\max {\bigl \{}|V(G)|:\Delta (G)\leq d,\ \operatorname {diam} (G)\leq k{\bigr \}},} {\displaystyle n_{d,k}=\max {\bigl \{}|V(G)|:\Delta (G)\leq d,\ \operatorname {diam} (G)\leq k{\bigr \}},}

where Δ ( G ) {\displaystyle \Delta (G)} {\displaystyle \Delta (G)} denotes the maximum degree of G {\displaystyle G} {\displaystyle G}. The elementary cases are

n d , 1 = d + 1 , n 1 , k = 2 , n 2 , k = 2 k + 1. {\displaystyle n_{d,1}=d+1,\qquad n_{1,k}=2,\qquad n_{2,k}=2k+1.} {\displaystyle 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.[1]

To obtain an upper bound, fix a vertex v {\displaystyle v} {\displaystyle v}. There are at most d {\displaystyle d} {\displaystyle d} vertices at distance one from v {\displaystyle v} {\displaystyle v}, and at most d ( d − 1 ) i − 1 {\displaystyle d(d-1)^{i-1}} {\displaystyle d(d-1)^{i-1}} vertices at distance i {\displaystyle i} {\displaystyle i}, since each vertex other than v {\displaystyle v} {\displaystyle v} has at most d − 1 {\displaystyle d-1} {\displaystyle d-1} edges leading farther away from v {\displaystyle v} {\displaystyle v}. Consequently,

n d , k ≤ M d , k = 1 + d ∑ i = 0 k − 1 ( d − 1 ) i , {\displaystyle n_{d,k}\leq M_{d,k}=1+d\sum _{i=0}^{k-1}(d-1)^{i},} {\displaystyle n_{d,k}\leq M_{d,k}=1+d\sum _{i=0}^{k-1}(d-1)^{i},}

where M d , k {\displaystyle M_{d,k}} {\displaystyle M_{d,k}} is the Moore bound. Equivalently,

M d , k = { 1 + d ( d − 1 ) k − 1 d − 2 , d ≥ 3 , 2 k + 1 , d = 2 , 2 , d = 1. {\displaystyle M_{d,k}={\begin{cases}1+d\displaystyle {\frac {(d-1)^{k}-1}{d-2}},&d\geq 3,\\[6pt]2k+1,&d=2,\\2,&d=1.\end{cases}}} {\displaystyle M_{d,k}={\begin{cases}1+d\displaystyle {\frac {(d-1)^{k}-1}{d-2}},&d\geq 3,\\[6pt]2k+1,&d=2,\\2,&d=1.\end{cases}}}

For every fixed k {\displaystyle k} {\displaystyle k},

M d , k = d k + O k ( d k − 1 ) {\displaystyle M_{d,k}=d^{k}+O_{k}(d^{k-1})} {\displaystyle M_{d,k}=d^{k}+O_{k}(d^{k-1})}

as d → ∞ {\displaystyle d\to \infty } {\displaystyle d\to \infty }.[1]

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.[4]

Complete graphs K d + 1 {\displaystyle K_{d+1}} {\displaystyle K_{d+1}} are Moore graphs of diameter one, and the odd cycles C 2 k + 1 {\displaystyle C_{2k+1}} {\displaystyle C_{2k+1}} 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.[5] Damerell and, independently, Bannai and Ito proved that there are no Moore graphs other than cycles with diameter at least three.[6][7]

For a graph G {\displaystyle G} {\displaystyle G} of maximum degree at most d {\displaystyle d} {\displaystyle d} and diameter at most k {\displaystyle k} {\displaystyle k}, the quantity

δ ( G ) = M d , k − | V ( G ) | {\displaystyle \delta (G)=M_{d,k}-|V(G)|} {\displaystyle \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.[1]

Bounds and constructions

Research on the degree–diameter problem proceeds in two complementary directions. Upper bounds and nonexistence results restrict the possible order of a graph, while explicit or probabilistic constructions provide lower bounds on n d , k {\displaystyle n_{d,k}} {\displaystyle n_{d,k}}.[1]

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.[1]

Asymptotic behaviour

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

Fixed degree

For d = 2 {\displaystyle d=2} {\displaystyle d=2}, the exact value is n 2 , k = 2 k + 1 {\displaystyle n_{2,k}=2k+1} {\displaystyle n_{2,k}=2k+1}. For every fixed d ≥ 3 {\displaystyle d\geq 3} {\displaystyle d\geq 3}, Bollobás and Fernandez de la Vega showed that almost every d {\displaystyle d} {\displaystyle d}-regular graph on n {\displaystyle n} {\displaystyle n} vertices has diameter

( 1 + o ( 1 ) ) log d − 1 ⁡ n {\displaystyle (1+o(1))\log _{d-1}n} {\displaystyle (1+o(1))\log _{d-1}n}

as n → ∞ {\displaystyle n\to \infty } {\displaystyle n\to \infty }.[8][9]

Together with the Moore bound, this gives

n d , k = ( d − 1 ) k + o ( k ) {\displaystyle n_{d,k}=(d-1)^{k+o(k)}} {\displaystyle n_{d,k}=(d-1)^{k+o(k)}}

as k → ∞ {\displaystyle k\to \infty } {\displaystyle k\to \infty } for each fixed d ≥ 3 {\displaystyle d\geq 3} {\displaystyle d\geq 3}. 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 {\displaystyle n_{d,k}/M_{d,k}} {\displaystyle n_{d,k}/M_{d,k}}.

Fixed diameter

For fixed k {\displaystyle k} {\displaystyle k}, Delorme introduced the parameter

μ k = lim inf d → ∞ n d , k d k . {\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}.} {\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}.}

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

μ 1 = μ 2 = μ 3 = μ 5 = 1 {\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1} {\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1}

and that

μ 4 ≥ 1 4 . {\displaystyle \mu _{4}\geq {\frac {1}{4}}.} {\displaystyle \mu _{4}\geq {\frac {1}{4}}.}[1]

For every fixed k ≥ 2 {\displaystyle k\geq 2} {\displaystyle k\geq 2}, Bollobás conjectured that

lim sup d → ∞ n d , k d k = 1. {\displaystyle \limsup _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1.} {\displaystyle \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 → ∞ n d , k d k = 1 {\displaystyle \lim _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1} {\displaystyle \lim _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1}

for every fixed positive integer k {\displaystyle k} {\displaystyle k}. Equivalently,

μ k = 1 {\displaystyle \mu _{k}=1} {\displaystyle \mu _{k}=1}

and

lim d → ∞ n d , k M d , k = 1 {\displaystyle \lim _{d\to \infty }{\frac {n_{d,k}}{M_{d,k}}}=1} {\displaystyle \lim _{d\to \infty }{\frac {n_{d,k}}{M_{d,k}}}=1}

for every fixed k {\displaystyle k} {\displaystyle k}.[2]

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

Relation to the degree–girth problem

The related degree–girth problem asks for the smallest possible order of a regular graph with prescribed degree and girth. For a d {\displaystyle d} {\displaystyle d}-regular graph of odd girth 2 k + 1 {\displaystyle 2k+1} {\displaystyle 2k+1}, breadth-first counting gives M d , k {\displaystyle M_{d,k}} {\displaystyle M_{d,k}} as a lower bound on its order. A graph attaining this lower bound is simultaneously a cage and a Moore graph.[1]

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

Directed and restricted variants

For a directed graph of maximum out-degree at most d {\displaystyle d} {\displaystyle d} and directed diameter at most k {\displaystyle k} {\displaystyle k}, the directed Moore bound is

M d , k → = 1 + d + d 2 + ⋯ + d k = { d k + 1 − 1 d − 1 , d > 1 , k + 1 , d = 1. {\displaystyle M_{d,k}^{\rightarrow }=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}}} {\displaystyle M_{d,k}^{\rightarrow }=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 {\displaystyle d=1} {\displaystyle d=1}, represented by directed cycles, and k = 1 {\displaystyle k=1} {\displaystyle k=1}, represented by complete digraphs.[1]

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.[1]

Known values and open problems

Exact values of n d , k {\displaystyle n_{d,k}} {\displaystyle n_{d,k}} 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.[1]

The existence of a Moore graph of degree 57 and diameter 2 remains open. Other questions concern the optimal rate at which n d , k / d k {\displaystyle n_{d,k}/d^{k}} {\displaystyle n_{d,k}/d^{k}} tends to one for fixed k {\displaystyle k} {\displaystyle k}, and the regime in which both degree and diameter tend to infinity. In particular, it is unknown whether

n d , k M d , k ⟶ 1 {\displaystyle {\frac {n_{d,k}}{M_{d,k}}}\longrightarrow 1} {\displaystyle {\frac {n_{d,k}}{M_{d,k}}}\longrightarrow 1}

along every sequence for which both d {\displaystyle d} {\displaystyle d} and k {\displaystyle k} {\displaystyle k} tend to infinity, and whether the Moore gap

M d , k − n d , k {\displaystyle M_{d,k}-n_{d,k}} {\displaystyle M_{d,k}-n_{d,k}}

is unbounded.[11][2]

See also

References

  1. Miller, Mirka; Širáň, Jozef (2013). "Moore Graphs and Beyond: A Survey of the Degree/Diameter Problem". Electronic Journal of Combinatorics. 20 (2). Dynamic Survey DS14, version 2. doi:10.37236/35.
  2. Cames van Batenburg, Wouter; Korsky, Samuel (4 August 2026). "Asymptotically attaining the Moore bound". arXiv:2608.03965 [math.CO].
  3. Elspas, Bernard (1964). "Topological constraints on interconnection-limited logic". Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design. IEEE. pp. 133–137.
  4. Singleton, Robert R. (1968). "There Is No Irregular Moore Graph". American Mathematical Monthly. 75 (1): 42–43. doi:10.2307/2315106. JSTOR 2315106.
  5. Hoffman, Alan J.; Singleton, Robert R. (1960). "On Moore Graphs with Diameters 2 and 3". IBM Journal of Research and Development. 4 (5): 497–504. doi:10.1147/rd.45.0497.
  6. Damerell, R. M. (1973). "On Moore graphs". Mathematical Proceedings of the Cambridge Philosophical Society. 74 (2): 227–236. doi:10.1017/S0305004100048015.
  7. Bannai, Eiichi; Ito, Tatsuro (1973). "On finite Moore graphs". Journal of the Faculty of Science, the University of Tokyo, Section IA, Mathematics. 20 (2): 191–208. doi:10.15083/00039786.
  8. Bollobás, Béla; Fernandez de la Vega, W. (1982). "The diameter of random regular graphs". Combinatorica. 2 (2): 125–134. doi:10.1007/BF02579310.
  9. Shimizu, Nobutaka (2020). "The average distance and the diameter of dense random regular graphs". Electronic Journal of Combinatorics. 27 (3). Paper P3.62. doi:10.37236/8705.
  10. Cames van Batenburg, Wouter; Korsky, Samuel (2026). "Asymptotically attaining the Moore bound — Lean 4 formalization". GitHub. Retrieved 7 August 2026.
  11. Bermond, Jean-Claude; Bollobás, Béla (1981). "The diameter of graphs: A survey". Congressus Numerantium. 32: 3–27.