次数直径問題

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

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

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

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

 参考文献 






 関連項目 
 Cage（英語）
 Table of degree diameter graphs（英語）
 Table of vertex-symmetric degree diameter digraphs（英語）
 Maximum degree-and-diameter-bounded subgraph problem（英語）

Category:グラフ理論
Category:数学に関する記事