重みつきグラフにおける新しい重み付け条件に関する研究

本年度は、昨年度に行った「禁止部分グラフと2-因子との関係」に関する研究を発展させ、「禁止部分グラフと因子との関係」について中心的に研究を進めた。以下、得られた結果について具体的に述べる。あるグラフHに対して「頂点数が十分大きい偶数のグラフGがH-フリーであるならば1-因子を持つ」という命題を考えた際、この命題を成り立たせるHはスターのみであることが知られており、またGに連結度の条件を加えた場合でもそれぞれの連結度に応じて適当なHのサイズが決定されている。この研究を動機として、二つのグラフを禁止した場合の適当な禁止部分グラフのペアについて研究がなされていた。しかしながら、禁止部分グラフのペアの完全な決定は連結度が低い場合のみなされており、連結度の高いグラフにおいては全容が解明されていなかった。本研究ではこの全容を解明し、連結度に応じた適当な禁止部分グラフのペアを完全に決定した。また、得られた結果は既存の結果のアナロジーとはなっておらず、これまでに予測できなかったペアが出現することが示されている。これはこの分野の今後の研究における一つの転換点となることが予想され、興味深い結果であると言える。また、2-因子についても同様に、二つの禁止部分グラフを用いた際の適当な禁止部分グラフのペアについて調べた。この問題については先行研究がなかったものの、1-因子の場合と似た性質が得られるとともに2-因子特有の性質についても明らかになり、今後の研究への広がりを期待させる結果となっている。

本年度は、昨年度に行った「禁止部分グラフと2-因子との関係」に関する研究を発展させ、「禁止部分グラフと因子との関係」について中心的に研究を進めた。以下、得られた結果について具体的に述べる。あるグラフHに対して「頂点数が十分大きい偶数のグラフGがH-フリーであるならば1-因子を持つ」という命題を考えた際、この命題を成り立たせるHはスターのみであることが知られており、またGに連結度の条件を加えた場合でもそれぞれの連結度に応じて適当なHのサイズが決定されている。この研究を動機として、二つのグラフを禁止した場合の適当な禁止部分グラフのペアについて研究がなされていた。しかしながら、禁止部分グラフのペアの完全な決定は連結度が低い場合のみなされており、連結度の高いグラフにおいては全容が解明されていなかった。本研究ではこの全容を解明し、連結度に応じた適当な禁止部分グラフのペアを完全に決定した。また、得られた結果は既存の結果のアナロジーとはなっておらず、これまでに予測できなかったペアが出現することが示されている。これはこの分野の今後の研究における一つの転換点となることが予想され、興味深い結果であると言える。また、2-因子についても同様に、二つの禁止部分グラフを用いた際の適当な禁止部分グラフのペアについて調べた。この問題については先行研究がなかったものの、1-因子の場合と似た性質が得られるとともに2-因子特有の性質についても明らかになり、今後の研究への広がりを期待させる結果となっている。