重みつきグラフにおける重いサイクルの存在やRamsey問題に関する研究

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

本研究は、一般のグラフの持つ性質と重みつきグラフの持つ性質の違いを「サイクル問題」「Ramsey問題」という2つの視点から解明することを目的としていた。本年度は2年計画の2年目にあたり、特にサイクル問題に関して多くの知見が得られたため、以下においてはサイクル問題に関する研究成果を述べる。重みつきグラフにおける重いサイクルの存在に関して、Dirac型条件を用いたBondy&Fanの定理に比べてOre型条件を用いたBondyらの定理は、用いる条件が弱まったために得られる結論が弱くなっていた。本研究では、結論が弱まる理由の本質的な部分を解明することにより、Bondy&Fanの定理のOre型条件を用いた拡張、さらにはOre型条件よりさらに弱い条件を用いた拡張となる定理を証明した。また、指定した頂点を通る重いサイクルの存在に関して、Dirac型条件では2-連結グラフにおいて指定した2頂点を通る重いサイクルの存在が知られていた。またOre型条件では、2-連結グラフにおいて指定した1頂点を通る重いサイクルの存在が示されていたが、上述したように得られる結論がDirac型条件を用いたものより弱いものであった。本研究では、Ore型条件を用いて2-連結グラフにおいて指定した2頂点を通る重いサイクルの存在を、Dirac型の定理の拡張となる形で証明した。この定理の証明において、Ore型条件を用いた際の特有の議論がなされており、今後の研究において特にσ_k型条件への拡張につながることが期待される結果である。