次数直径問題とは？わかりやすく解説

次数直径問題（じすうちょっけいもんだい）とは、グラフ理論において最大次数がdで直径がkのグラフのうち頂点数が最大となるグラフGを見つけよ、というものである。Gの頂点数はムーア・バウンドによって上から抑えられる。1<kで2<dのときムーアバウンドに一致するグラフ（ムーアグラフ）で構成できているものはピーターセングラフとホフマンシングルトングラフである。k=2でd=57のときにムーアバウンドに一致するグラフが存在しうるが、いまだ構成されておらず未解決の問題である。一般的に最大次数と直径が与えられたときの最大頂点数はムーアバウンドよりも小さくなる。

ムーアバウンド

最大次数dと直径kのグラフのうち最大の頂点数を $n_{d,k}$ とする。 $n_{d,k}\leq M_{d,k}$ となる $M_{d,k}$ はムーアバウンドと呼ばれ以下のようになる。

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}$ の漸近的な振る舞いは $M_{d,k}=d^{k}+O(d^{k-1})$ となる。

$\mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}$ について考えよう。任意のkに対して $\mu _{k}=1$ と予想されている。 $\mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1$ と $\mu _{4}\geq 1/4$ については既に証明されている。また一般的に $\mu _{k}\geq 1.6^{k}$ が成り立つ。