次数直径問題
最大次数dと直径kのグラフのうち最大の頂点数を n d , k {\displaystyle n_{d,k}} とする。 n d , k ≤ M d , k {\displaystyle n_{d,k}\leq M_{d,k}} となる M d , k {\displaystyle M_{d,k}} はムーアバウンドと呼ばれ以下のようになる。
M d , k = { 1 + d ( d − 1 ) k − 1 d − 2 if d > 2 2 k + 1 if d = 2 {\displaystyle M_{d,k}={\begin{cases}1+d{\frac {(d-1)^{k}-1}{d-2}}&{\text{ if }}d>2\\2k+1&{\text{ if }}d=2\end{cases}}}
ムーアバウンドに到達するグラフは非常に少ないことが示されている。
M d , k {\displaystyle M_{d,k}} の漸近的な振る舞いは M d , k = d k + O ( d k − 1 ) {\displaystyle M_{d,k}=d^{k}+O(d^{k-1})} となる。
μ k = lim inf d → ∞ n d , k d k {\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}} について考えよう。任意のkに対して μ k = 1 {\displaystyle \mu _{k}=1} と予想されている。 μ 1 = μ 2 = μ 3 = μ 5 = 1 {\displaystyle \mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1} と μ 4 ≥ 1 / 4 {\displaystyle \mu _{4}\geq 1/4} については既に証明されている。また一般的に μ k ≥ 1.6 k {\displaystyle \mu _{k}\geq 1.6^{k}} が成り立つ。