次数直径問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

ムーアバウンド[編集]

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

ムーアバウンドに到達するグラフは非常に少ないことが示されている。の漸近的な振る舞いは  となる。

について考えよう。任意のkに対して  と予想されている。  と については既に証明されている。また一般的に が成り立つ。

関連項目[編集]

参考文献[編集]

  • Bannai, E.; Ito, T. (1973), “On Moore graphs”, J. Fac. Sci. Univ. Tokyo Ser. A 20: 191–208, MR0323615