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

加权图中重环的存在性及Ramsey问题研究

基本信息

批准号：
04J07558
负责人：
藤沢潤
金额：
$ 1.22万
依托单位：
Keio University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-04J07558/
关键词：
グラフ重みつきグラフ閉路ラムゼー問題内周

项目摘要

本研究は、一般のグラフの持つ性質と重みつきグラフの持つ性質の違いを「サイクル問題」「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型条件への拡張につながることが期待される結果である。

本研究的目的是从“循环问题”和“拉姆齐问题”两个角度阐明一般图和加权图性质之间的差异。今年是两年计划的第二年，我们学到了很多知识，特别是关于循环问题，所以下面我们将介绍关于循环问题的研究成果。关于加权图中重循环的存在，与使用狄拉克型条件的Bondy & Fan定理相比，使用Ore型条件的Bondy等人的定理由于所使用的条件较弱，所以结论较弱。在本研究中，通过阐明结论被削弱的本质原因，我们证明了使用Ore型条件的Bondy＆Fan定理的扩展，以及使用比Ore型条件更弱的条件的扩展。关于通过指定顶点的重环的存在性，已知在狄拉克型条件下，2连通图中存在通过两个指定顶点的重环。另外，Ore型条件显示了2连通图中存在通过指定顶点的重循环，但如上所述，得到的结论比使用Dirac型条件得到的结论弱。在本研究中，我们使用 Ore 型条件证明了通过 2 连通图中两个指定顶点的重循环的存在，其形式是狄拉克型定理的扩展。在该定理的证明中，对使用Ore型条件进行了独特的讨论，该结果有望在未来的研究中推广到σ_k型条件。