グラフのタフネス,平面性と次数を制限した全域木の関係

点击翻译按钮获取中文摘要

論文2では当研究課題の目的の一つである,「トーラス上の任意の4-連結グラフはハミルトン閉路を持つ」というGrunbaum, Nash-Williams予想に関して,重要な部分的解決を与えている.Tutteの平面グラフの結果以降,閉曲面上のグラフのハミルトン性に関してさまざまな結果が示されてきたが,Grunbaum, Nash-Williamsの予想は40年以上前に予想された重要な未解決問題である.この予想の難しさの一因は,平面や射影平面上では現れなかった,トーラス上の4-連結グラフで「タフネスがちょうど1」であるものが存在する,という事実である.通常,ハミルトン閉路に関する問題は,帰納法を適用する都合上,「ハミルトン閉路を持つ」よりも強い性質を示す方が良い場合が多く,実際に平面・射影平面の結果は全てそのような手法で証明されている.しかし,そのようなより強い性質は「タフネスがちょうど1」であるグラフでは,少数の例外を除き,成り立たないことが示されているため,平面や射影平面では考慮する必要のない,「タフネスがちょうど1となるグラフ」が,既存の手法を適用するための障害となっていた.この点を考慮し,われわれは既存の研究とは根本的に異なる手法を提案することで,「トーラス上の任意の4・連結グラフは,タフネスがちょうど1ならば,ハミルトン閉路を持つ」という結果を示している.したがって,Grunbaum, Nash-Williams予想の解決のためには,タフネスが1でないグラフのみを考慮すれば良く,そこで平面や射影平面の場合に成功した既存の手法を用いることができる可能性がある.上記した以外にも,Grunbaum, Nash-Williams予想に関連して,本年度はいくつかの結果も得ている