ハミルトン性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:46 UTC 版)
立方体グラフのハミルトン性については多くの研究結果がある。1980年にP.G. テイト（英語版）は、すべての立方多面体グラフはハミルトン閉路を持つと予想した。このテイトの予想に対する反例は、ウィリアム・トーマス・トゥッテ（英語版）の 46-頂点タットグラフによって、1946年に挙げられた。そのトゥッテは 1971年、すべての 2部立方体グラフはハミルトンであると予想した。しかし、ジョセフ・ホートンは 96-頂点ホートングラフ（英語版）をこの反例として挙げた。その後、マーク・エリンガムはさらに二つの反例を挙げた：エリンガム-ホートングラフ（英語版）である。未だに解決のなされていない、テイトとトゥッテの予想の組合せであるバーネットの予想（英語版）では、すべての二部立方多面体グラフはハミルトンである、としている。立方体グラフがハミルトンであるとき、LCF表記（英語版）によってそれを正確に表現することが出来る。 すべての n-頂点立方体グラフの中から一様にランダムに（英語版）一つの立方体グラフが選ばれるとき、それはハミルトンであることが非常に多い： n が無限大へと向かう極限において、n-頂点立方体グラフがハミルトンである割合は 1 となる。 デビッド・エプシュタイン（英語版）は、すべての n-頂点立方体グラフは多くとも 2n/3 個（およそ 1.260n 個）の異なるハミルトン閉路を含むと予想し、そのような多くの閉路を含む立方体グラフの例を提供した。異なるハミルトン閉路の数について証明された最良の上界は、1.276n である。
※この「ハミルトン性」の解説は、「立方体グラフ」の解説の一部です。
「ハミルトン性」を含む「立方体グラフ」の記事については、「立方体グラフ」の概要を参照ください。
- ハミルトン性のページへのリンク
