並列タイトル等{a,b}-factors of regular graphs
一般注記text/plain
application/pdf
研究報告書
研究成果の概要（和文）：aとbとrはa+b=r, a≦r/2を満たす正の整数とする。課題はrが奇数のときに、予想「r-正則グラフには{a,b}-因子が存在する」ことを示すことである。同時に関連するグラフ理論の問題に貢献することである。これに対して、もしaが偶数で2≦a≦r/2ならこの予想が成り立つことを示した。また、もしaが奇数r/3≦a≦r/2なら予想が成り立つことを示した。最近もしaが奇数で(a+1)(a+2)≦rなら予想が成り立たないことが示された。しかし未解決な場合が残っている。また関連する2部グラフの因子、一般のグラフの因子およびグラフの全域木についてもいくつかの結果を得た。
研究成果の概要（英文）：Let a, b and r be positive integers such that a+b=r and a≦r/2. We want to prove the following conjecture: If r is odd, then every r-regular graph has an {a,b}-factor. We showed that if either a is even or a is odd and r/3≦a≦r/2, then the conjecture holds. On the other, it was recently shown that the conjecture does not hold if (a+1)(a+2)≦r. However there are unsolved cases. We also
obtained some results on factors of graphs and spanning trees of graph, which are related to the above conjecture.
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）