有向グラフ上の詰込み・分割問題に対する新手法の開発とその応用

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

(1) 指定された個数からなる指定された長さの有向閉路詰込みに対する次数条件1984年にEl-Zaharによって提起された「指定された個数からなる指定された長さの閉路分割」に対する次数条件を有向グラフ版へと拡張する方法について検討することで、「指定された個数からなる指定された奇数長の有向閉路詰め込み」に対する最良な次数条件を、前年度までに定めていた方針によって実際に与えることに成功した。本研究成果は、閉路詰込み問題に関する1997年のBrandtらの結果（J. Graph Theory）および2018年のChiba-Yamashitaの結果（SIAM J. Discrete Math.）の共通の一般化となるものであり、詰込み問題に対する新手法の開発において新たな知見を見出したといえる。(2) ハミルトン閉路の一般化およびグラフの連結度と独立数有向閉路分割問題に対する新たな研究の方向性を模索するために、無向グラフ上のハミルトン閉路問題に関する既存の研究成果の精査を行なった。特に、ハミルトン閉路や辺支配閉路、指定された頂点を通る閉路など、閉路に関する多くの概念を包括する“intersecting cycle”と呼ばれる新しい閉路の概念を導入し、その閉路の存在性に対するグラフの連結度と独立数の関係を明らかにし、学術雑誌（Discrete Math., 2022）を通してその研究成果を発表した。(3) グラフの分割問題および関連問題における十分条件グラフ上の閉路分割数・道分割数に対する禁止部分グラフ条件や星グラフの族の分割に対するグラフの最小次数とサイズに関する条件等について考察し、学術雑誌（Electron. J. Combin., 2022 & Graphs Combin., 2023）を通してその研究成果を発表した。