密なグラフの構造把握のための連結度と禁止部分グラフに関する研究

今年度は前年度に引き続き,点素な星グラフの存在に関する江川-太田予想の解決にむけて禁止部分グラフの観点から研究を進めた。その結果,以下の定理を得ることが出来,今年度Discrete Mathematicsに論文として出版された.定理.kを2以上め整数とする.位数7-6上,最小次数3以上のK_<1,3>を誘導部分グラフとして含まない任意のグラフは点素なK_1+(K_1UK_2)をk個含む.この定理における位数・最小次数の条件はともに最善であり,H.Wangによって得られていたK_<1,3>を誘導部分グラフとして含まないグラフの族における点素な三角形の存在に関する結果の位数が大きいときの拡張にもなっている.さらに,この結果は,研究代表者が提起したK_<1,t>を誘導部分グラフとして含まないグラフのクラスにおける同様の問題に関する部分的解決を与えており,禁止部分グラフのこの種の極値問題研究に関して新たな進展を与えたと言える.また,密なグラフの内部では,グラフめ連結度が部分的に高くなり,そのような高連結部分グラフの構造把握の重要性から,本研究ではグラフの連結度に関しても並行して研究を進めていた.その結果,除去しても連結度が下がらないような辺が存在するための十分条件としてのグラフの次数条件についてもほぼ最善の値を決定することに成功した.さらに,禁止部分グラフの研究と関連して,縮約しても連結度が下がらない辺もしくは三角形が存在するための禁止部分グラフを決定するという問題に対しても新しい結果を得ることが出来,Journal of Graph Theoryに論文として出版された.

今年度は前年度に引き続き,点素な星グラフの存在に関する江川-太田予想の解決にむけて禁止部分グラフの観点から研究を進めた。その結果,以下の定理を得ることが出来,今年度Discrete Mathematicsに論文として出版された.定理.kを2以上め整数とする.位数7-6上,最小次数3以上のK_<1,3>を誘導部分グラフとして含まない任意のグラフは点素なK_1+(K_1UK_2)をk個含む.この定理における位数・最小次数の条件はともに最善であり,H.Wangによって得られていたK_<1,3>を誘導部分グラフとして含まないグラフの族における点素な三角形の存在に関する結果の位数が大きいときの拡張にもなっている.さらに,この結果は,研究代表者が提起したK_<1,t>を誘導部分グラフとして含まないグラフのクラスにおける同様の問題に関する部分的解決を与えており,禁止部分グラフのこの種の極値問題研究に関して新たな進展を与えたと言える.また,密なグラフの内部では,グラフめ連結度が部分的に高くなり,そのような高連結部分グラフの構造把握の重要性から,本研究ではグラフの連結度に関しても並行して研究を進めていた.その結果,除去しても連結度が下がらないような辺が存在するための十分条件としてのグラフの次数条件についてもほぼ最善の値を決定することに成功した.さらに,禁止部分グラフの研究と関連して,縮約しても連結度が下がらない辺もしくは三角形が存在するための禁止部分グラフを決定するという問題に対しても新しい結果を得ることが出来,Journal of Graph Theoryに論文として出版された.