次数直径問題

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

ムーアバウンド

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

${\displaystyle M_{d,k}={\begin{cases}1+d{\frac {(d-1)^{k}-1}{d-2}}&{\text{ if }}d>2\\2k+1&{\text{ if }}d=2\end{cases}}}$

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

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

関連項目

• Cage（英語）
• Table of degree diameter graphs（英語）
• Table of vertex-symmetric degree diameter digraphs（英語）
• Maximum degree-and-diameter-bounded subgraph problem（英語）

参考文献

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

• Hoffman, Alan J.; Singleton, Robert R. (1960), “Moore graphs with diameter 2 and 3”, IBM Journal of Research and Development 5 (4): 497–504, doi:10.1147/rd.45.0497, MR0140437, http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf 

• Singleton, Robert R. (1968), “There is no irregular Moore graph”, American Mathematical Monthly (Mathematical Association of America) 75 (1): 42–43, doi:10.2307/2315106, MR0225679, http://www.jstor.org/stable/2315106 

• Miller, Mirka; Širáň, Jozef (2005), “Moore graphs and beyond: A survey of the degree/diameter problem”, Electronic Journal of Combinatorics Dynamic survey: DS14, http://www.combinatorics.org/Surveys/ds14.pdf 

• CombinatoricsWiki - The Degree/Diameter Problem, http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem