4-連結射影平面的グラフのハミルトン連結性(特別企画)
スポンサーリンク
概要
- 論文の詳細を見る
グラフGにおいて,任意の2頂点ν,νに対しGがνとνを結ぶハミルトン道を持つとき,Gはハミルトン連結であるという.本講演では次の結果を示す.射影平面上の任意の4-連結グラフはハミルトン連結である.これはDeanの予想[1]の肯定的な解決であり,また以下の二つの結果の共通の拡張である.(1)平面上の任意の4-連結グラフはハミルトン連結である(Thomassen[3],なお,これは「平面上の任意の4一連結グラフはハミルトン閉路を持つ」というTutte[4]の結果の拡張である).(2)射影平面上の任意の4-連結グラフはハミルトン閉路を持つ(Thomas&Yu[2]).またこれは,連結度を3以下にできない,かつ,より種数の高い閉曲面上のグラフへは拡張できない,という意味で最善である.(すなわち,トーラス上の4一連結グラフでハミルトン連結でないものが存在する.)上の定理の証明は構成的であり,与えられた射影平面上の4-連結グラフと2頂点賜,νに対し,νとνを結ぶハミルトン道を多項式時間(0(n^2)時間)で見つけるアルゴリズムを与えている.
- 一般社団法人電子情報通信学会の論文
- 2012-12-03
著者
関連論文
- 2-F-10 平面グラフ上の誘導サイクル問題に対する解法(グラフ(1))
- グラフ理論の応用 (現代数学はいかに使われているか--代数編)
- DS-1-8 A spanning closed walk of 3-connected plane graphs
- 4-連結射影平面的グラフのハミルトン連結性(特別企画)
- 2-F-2 二部グラフ上の最適予算配分問題に対する高速アルゴリズム(離散最適化(4))
- JST ERATO「河原林巨大グラフ」プロジェクトの目指す方向