次数直径問題のソースを表示

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

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

:<math>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}</math>

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

<math>\mu_k=\liminf_{d\to\infty}\frac{n_{d,k}}{d^k}</math>について考えよう。任意のkに対して <math>\mu_k=1</math> と予想されている。 <math>\mu_1=\mu_2=\mu_3=\mu_5=1</math> と <math>\mu_4\geq 1/4</math>については既に証明されている。また一般的に <math>\mu_k\geq 1.6^k</math>が成り立つ。

== 関連項目 ==
* [[:en:Cage (graph theory)|Cage（英語）]]
* [[:en:Table of the largest known graphs of a given diameter and maximal degree|Table of degree diameter graphs（英語）]]
* [[:en:Table of vertex-symmetric digraphs|Table of vertex-symmetric degree diameter digraphs（英語）]]
* [[:en:MaxDDBS|Maximum degree-and-diameter-bounded subgraph problem（英語）]]

== 参考文献 ==
* {{Citation|last1 = Bannai|first1 = E.|last2 = Ito|first2 = T.|title = On Moore graphs|journal = J. Fac. Sci. Univ. Tokyo Ser. A|volume = 20|pages = 191–208|year = 1973|mr = 0323615}}

* {{Citation|author1-link = Alan Hoffman (mathematician)|last1 = Hoffman|first1 = Alan J.|last2 = Singleton|first2 = Robert R.|title = Moore graphs with diameter 2 and 3|journal = IBM Journal of Research and Development|volume = 5|issue = 4|year = 1960|pages = 497–504|url = http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf|mr = 0140437|doi = 10.1147/rd.45.0497}}

* {{Citation|title = There is no irregular Moore graph|last = Singleton|first = Robert R.|journal = [[American Mathematical Monthly]]|volume = 75|issue = 1|pages = 42–43|year = 1968|url = http://www.jstor.org/stable/2315106|mr = 0225679|doi = 10.2307/2315106|publisher = Mathematical Association of America}}

* {{Citation|last1 = Miller|first1 = Mirka|last2 = Širáň|first2 = Jozef|title = Moore graphs and beyond: A survey of the degree/diameter problem|journal = [[Electronic Journal of Combinatorics]]|volume = Dynamic survey|pages = DS14|year = 2005|url = http://www.combinatorics.org/Surveys/ds14.pdf}}

* {{Citation|title = CombinatoricsWiki - The Degree/Diameter Problem|url = http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem}}

{{デフォルトソート:しすうちよつけいもんたい}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]