次数直径問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/07/04 20:41 UTC 版)
グラフ理論において、次数直径問題とは、最大次数がdで直径がkのグラフのうち頂点数が最大となるグラフGを見つけよ、というものだ。Gの頂点数はムーア・バウンドによって上から抑えられる。1<kで2<dのときムーアバウンドに一致するグラフ(ムーアグラフ)で構成できているものはピーターセングラフとホフマンシングルトングラフである。k=2でd=57のときにムーアバウンドに一致するグラフが存在しうるが、いまだ構成されておらず未解決の問題である。一般的に最大次数と直径が与えられたときの最大頂点数はムーアバウンドよりも小さくなる。
- 1 次数直径問題とは
- 2 次数直径問題の概要
- 次数直径問題のページへのリンク