度-直径问题

度-直径问题是图论中一个问题，目的在定下最大直径k及最大度数d后，找出拥有最多节点的图。

假设图以${\displaystyle G=(V,E)}$表示，某节点的度数以${\displaystyle \deg(v)}$表示，节点之间的最短距离以${\displaystyle d(u,v)}$表示，则度-直径问题是规定了

${\displaystyle d\geq \max _{v\in V}\deg(v)}$

${\displaystyle k\geq \max _{u,v\in V}d(u,v)}$

求出图G。G的大小（以节点数衡量）受制于摩尔上限，亦即节点的数目不可能多于

${\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i}}$

已知在k > 1和d > 2的情况下，只有佩特森图和Hoffman-Singleton图（英语：Hoffman–Singleton graph），以及一个k=2、d=57的图能达到摩尔上限，一般情况下，图的节点数目远少于摩尔上限所指定。