Regularity Lemmaの禁止部分グラフ条件への適用

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

本研究の目的はRegularity Lemmaを禁止部分グラフ条件が課されたグラフに適用することである．目的達成のため，本研究では密なグラフや禁止部分グラフ条件の課されたグラフの構造解析をすることから始めた．そして，本研究に関係深い成果を5本の論文にまとめ，査読ありの国際誌に投稿した．そのうち3本が本年度にすでに受理されている．以下，本研究に関係する結果の詳細を記載する．1つ目の結果はグラフが与えられたkに対して超過数を制限した全域木をもつためのclosure型の次数条件に関する結果である．全域木の超過数は各頂点から出る辺の本数を制限した全域木の拡張研究である．そして，closure型の次数条件はOre型やFan型とよばれるいくつかの次数条件よりも弱い条件である．以上のことから本研究は概念としての拡張性，条件として弱さから非常に有用な結果といえる．本研究結果は国際誌Graphs and Combinatoricsに受理されている．2つ目の結果はグラフがk-leaf-connectedであるための次数条件に関する結果である．k-leaf-connectedという概念はハミルトン連結とよばれる巡回セールスマン問題とも深遠な関係にある概念の拡張である．本研究では既存の次数条件よりも弱い次数条件でグラフがk-leaf-connectedであることが保証できることを示した．本研究結果は国際誌Discrete Mathematicsに受理されている．3つ目はグラフが全域k-treeをもつための禁止部分グラフ条件に関する結果である．これは2010年に太田・杉山によってなされた全域k-treeをもつための禁止部分グラフペアの予想を肯定的に解決したものである．