並列タイトル等ヘイキョクメンジョウ ノ グラフ ニ オケル インシ モンダイ ノ ケンキュウ
Heikyokumenjō no gurafu ni okeru inshi mondai no kenkyū
On factor problems in graph on surfaces
一般注記type:text
本研究の主な成果を以下に挙げる。1)閉曲面上の3-連結3-正則2部グラフにおいて、互いに距離が十分離れたマッチングが拡張的となることが示された。2)ハミルトンサイクルを持たない1-toughな平面の三角形分割における分離三角形について、Ozeki-Zamfirescuの提起した問題が肯定的に解決された。3)閉曲面上の5-連結三角形分割からいくつかの頂点を取り除いたグラフにおける完全マッチングの存在について、Kawarabayashi-Plummer-Ozekiの定理を一般化した定理・Aldred-Kawarabayashi-Plummerの定理の短い証明とそれを一般化した定理が得られた。
The following is the main part of the results obtained in this research. Firstly, it turned out that every 3-conncted 3-regular bipartite graph on a surface is distance matchable. Secondly, the problem concerning separating 3-cycles in non-hamiltonian 1-tough triangulation of the plane, posed by Ozeki and Zamfirescu, was solved in the affirmative. Thirdly, as for the existence of the perfect matchings in graphs obtained from 5-connected triangulation of a surface by deleting some vertices, we obtained a generalization of the theorem shown by Kawarabayashi, Plummer and Ozeki. Moreover, we obtaind a short proof and a generalization of the theorem shown by Aldred, Kawarabayashi and Plummer.
研究種目 : 基盤研究 (C) (一般)
研究期間 : 2017~2020
課題番号 : 17K05349
研究分野 : グラフ理論
一次資料へのリンクURLhttps://koara.lib.keio.ac.jp/xoonips/modules/xoonips/download.php?koara_id=KAKEN_17K05349seika
連携機関・データベース国立情報学研究所 : 学術機関リポジトリデータベース(IRDB)(機関リポジトリ)