次数直径問題

グラフ理論において次数直径問題とは、最大次数が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{matrix} 1 + d \frac{(d - 1)^{k} - 1}{d - 2} & if d > 2 \\ 2 k + 1 & if d = 2 \end{matrix}

ムーアバウンドに到達するグラフは非常に少ないことが示されている。 $M_{d, k}$ の漸近的な振る舞いは $M_{d, k} = d^{k} + O (d^{k - 1})$ となる。

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