不変量から定まるグラフの部分構造について

グラフにハミルトン閉路があるかどうかを決定する問題は有名なNP-完全問題である.この問題へのアプローチには様々なものが,その一つの方法は,ハミルトン閉路への近さを(数量的に)評価する,というものである.本年度の研究では,特にk-tree/f-treeに関しての研究を行い,次の二つの結果を得ている.なお,k-treeとは最大次数がk以下の木であり,頂点集合から非負整数への写像fに対してのf-treeとは各頂点の次数がfの値以下であるような木である.k=2のとき,spanning k-treeとハミルトン道が一致しており,また,fが値kをとる恒等写像のときf-treeとk-treeが一致している.・spanning f-treeの存在のための新しい独立数型条件の提示.・3-連結K{3,t}-minor-freeグラフがt-treeを持つことの証明.また,ハミルトン閉路の拡張として,グラフのいくつかの頂点を指定し,その指定された頂点を全て通る閉路に関しての研究が行われているが,spanning k-treeを同様の方向に拡張し,指定された頂点を全て含むk-treeに関しての結果も得ている.・指定された頂点を全て含むようなk-treeが存在するための次数和型条件の提示.以上のように本年度は次数の制限された木の存在に関しての研究を中心的に行った.加えてこの観点から,次数が指定された値以上であるような全域木の存在に関しての研究も行っている.また,上記した以外にもグラフのcoloringの問題について等の研究も行い,論文にまとめている.

グラフにハミルトン閉路があるかどうかを決定する問題は有名なNP-完全問題である.この問題へのアプローチには様々なものが,その一つの方法は,ハミルトン閉路への近さを(数量的に)評価する,というものである.本年度の研究では,特にk-tree/f-treeに関しての研究を行い,次の二つの結果を得ている.なお,k-treeとは最大次数がk以下の木であり,頂点集合から非負整数への写像fに対してのf-treeとは各頂点の次数がfの値以下であるような木である.k=2のとき,spanning k-treeとハミルトン道が一致しており,また,fが値kをとる恒等写像のときf-treeとk-treeが一致している.・spanning f-treeの存在のための新しい独立数型条件の提示.・3-連結K{3,t}-minor-freeグラフがt-treeを持つことの証明.また,ハミルトン閉路の拡張として,グラフのいくつかの頂点を指定し,その指定された頂点を全て通る閉路に関しての研究が行われているが,spanning k-treeを同様の方向に拡張し,指定された頂点を全て含むk-treeに関しての結果も得ている.・指定された頂点を全て含むようなk-treeが存在するための次数和型条件の提示.以上のように本年度は次数の制限された木の存在に関しての研究を中心的に行った.加えてこの観点から,次数が指定された値以上であるような全域木の存在に関しての研究も行っている.また,上記した以外にもグラフのcoloringの問題について等の研究も行い,論文にまとめている.