グラフの大域構造に着目した極値問題の研究

グラフ理論における典型的な研究対象であるハミルトン閉路を始めとして，グラフに含まれる閉路に関する極値問題について研究を進めた。グラフにハミルトン閉路が存在するための必要条件をもとに定義された，タフネスの概念がある。タフネスは，グラフから取り除く頂点数とそれによって生じる連結成分数の比を用いて定義される。ハミルトン閉路を持つグラフは1-タフであることが容易にわかるが，タフネスがある定数以上のグラフはハミルトン閉路を持つであろう，というChvatal(1973)の予想は，この分野の大きな未解決問題である。本研究では，グラフのクラスを制限したところでのChvatal予想について考え，グラフ2K_2を禁止誘導部分グラフとするグラフについて予想が成り立つことを示した。禁止する誘導部分グラフをさらに緩和させた場合についての考察も引き続き行っている。グラフに含まれる閉路は，グラフの辺が増えるほどその種類が増えていく。その種類の増え方がどのような傾向を見せるのか，極値問題的な視点からの研究は古くから行われている。本研究では，グラフに与える条件としては最小次数条件を考え，k個の連続する長さの閉路，または公差2でk個連続する長さの閉路の存在について，既存の結果を改良する成果を得た。証明では，閉路を直接考えるのではなく，指定された2頂点を結ぶパスの長さに関する結果を巧妙な帰納法を用いて証明し，その系として閉路の長さに関する結果を得ている。研究成果については，2022年12月に開催された応用数学合同研究集会で発表した。また2023年2月には，慶應義塾大学において若手研究者らを交えた研究集会を開催し，関連する若手研究者と情報交換や研究討論を行った。

グラフ理論における典型的な研究対象であるハミルトン閉路を始めとして，グラフに含まれる閉路に関する極値問題について研究を進めた。グラフにハミルトン閉路が存在するための必要条件をもとに定義された，タフネスの概念がある。タフネスは，グラフから取り除く頂点数とそれによって生じる連結成分数の比を用いて定義される。ハミルトン閉路を持つグラフは1-タフであることが容易にわかるが，タフネスがある定数以上のグラフはハミルトン閉路を持つであろう，というChvatal(1973)の予想は，この分野の大きな未解決問題である。本研究では，グラフのクラスを制限したところでのChvatal予想について考え，グラフ2K_2を禁止誘導部分グラフとするグラフについて予想が成り立つことを示した。禁止する誘導部分グラフをさらに緩和させた場合についての考察も引き続き行っている。グラフに含まれる閉路は，グラフの辺が増えるほどその種類が増えていく。その種類の増え方がどのような傾向を見せるのか，極値問題的な視点からの研究は古くから行われている。本研究では，グラフに与える条件としては最小次数条件を考え，k個の連続する長さの閉路，または公差2でk個連続する長さの閉路の存在について，既存の結果を改良する成果を得た。証明では，閉路を直接考えるのではなく，指定された2頂点を結ぶパスの長さに関する結果を巧妙な帰納法を用いて証明し，その系として閉路の長さに関する結果を得ている。研究成果については，2022年12月に開催された応用数学合同研究集会で発表した。また2023年2月には，慶應義塾大学において若手研究者らを交えた研究集会を開催し，関連する若手研究者と情報交換や研究討論を行った。