次数直径問題

グラフ理論において次数直径問題とは、最大次数が"d"で直径が"k"のグラフのうち頂点数が最大となるグラフ"G"を見つけよ、というものだ。"G"の頂点数はムーア・バウンドによって上から抑えられる。1<"k"で2<"d"のときムーアバウンドに一致するグラフ（ムーアグラフ）で構成できているものはピーターセングラフとホフマンシングルトングラフである。"k"=2で"d"=57のときにムーアバウンドに一致するグラフが存在しうるが、いまだ構成されておらず未解決の問題である。一般的に最大次数と直径が与えられたときの最大頂点数はムーアバウンドよりも小さくなる。
ムーアバウンド.
最大次数"d"と直径"k"のグラフのうち最大の頂点数を formula_1 とする。 formula_2 となるformula_3はムーアバウンドと呼ばれ以下のようになる。
ムーアバウンドに到達するグラフは非常に少ないことが示されている。formula_3の漸近的な振る舞いは formula_6 となる。
formula_7について考えよう。任意のkに対して formula_8 と予想されている。 formula_9 と formula_10については既に証明されている。また一般的に formula_11が成り立つ。