正則性の高いグラフの部分構造に関する研究

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

本研究は平成21年度より2年間科学研究費補助金の援助を受け、今年度はその初年度である。今年度得られた成果は以下の通りである。1.P_3因子の存在を保つようなグラフの変形操作を用いることにより、「3-連結3-正則グラフの細分で、頂点数が3k+1点であり、1点取り除くとP_3因子が存在しないようなグラフ」の無限系列が得られた。2.禁止することにより得られるグラフが、有限個の例外を除いてK_{1,r}フリーとなるようなグラフの族を全てのrに対して決定した。3.禁止することにより、得られるk-連結グラフの族が有限個となるような2つのグラフのペアを、kが6以下の場合に決定した。4.トーラス上の4-正則グラフの双対グラフにおいて、以下の二つを同時に満たすようなグラフの局所変形操作「ladder-addition」を考案した。(1)2部グラフであったものを2部グラフでないものに変形する。(2)対象となるグラフのvertex-face curveの存在を保つ。1.で得られたグラフは3-連結3-正則グラフを分解して得られるものであり、支配数に関するReed予想の解明のための大きな手掛かりとなる。2.で得られたグラフの族は無限個あり、その結果自体が非常に興味深い上、2.と3.で得られた研究成果によってどのようなグラフの族が禁止部分グラフの族として本質的かが解明され、今後の禁止部分グラフを用いた研究に対して有益な情報を与える。また4.で得られた成果によって、トーラス上の2部グラフのハミルトン性の解明に向けて一つの見通しが得られた。このように本年度は「支配数」「禁止部分グラフ」「閉曲面上のグラフ」といった多角的な研究成果が得られた。