グラフの大域構造に着目した極値問題の研究

关注图全局结构的极值问题研究

基本信息

批准号：
22K03404
负责人：
太田克弘
金额：
$ 2.16万
依托单位：
Keio University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2026-03-31
项目状态：
未结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K03404/
关键词：
グラフ理論極値問題閉路大域構造

项目摘要

グラフ理論における典型的な研究対象であるハミルトン閉路を始めとして，グラフに含まれる閉路に関する極値問題について研究を進めた。グラフにハミルトン閉路が存在するための必要条件をもとに定義された，タフネスの概念がある。タフネスは，グラフから取り除く頂点数とそれによって生じる連結成分数の比を用いて定義される。ハミルトン閉路を持つグラフは1-タフであることが容易にわかるが，タフネスがある定数以上のグラフはハミルトン閉路を持つであろう，というChvatal(1973)の予想は，この分野の大きな未解決問題である。本研究では，グラフのクラスを制限したところでのChvatal予想について考え，グラフ2K_2を禁止誘導部分グラフとするグラフについて予想が成り立つことを示した。禁止する誘導部分グラフをさらに緩和させた場合についての考察も引き続き行っている。グラフに含まれる閉路は，グラフの辺が増えるほどその種類が増えていく。その種類の増え方がどのような傾向を見せるのか，極値問題的な視点からの研究は古くから行われている。本研究では，グラフに与える条件としては最小次数条件を考え，k個の連続する長さの閉路，または公差2でk個連続する長さの閉路の存在について，既存の結果を改良する成果を得た。証明では，閉路を直接考えるのではなく，指定された2頂点を結ぶパスの長さに関する結果を巧妙な帰納法を用いて証明し，その系として閉路の長さに関する結果を得ている。研究成果については，2022年12月に開催された応用数学合同研究集会で発表した。また2023年2月には，慶應義塾大学において若手研究者らを交えた研究集会を開催し，関連する若手研究者と情報交換や研究討論を行った。

我们对图所包含的环相关的极值问题进行了研究，其中包括哈密顿环，这是图论中的一个典型研究课题。有一个韧性的概念，它是根据图中存在哈密顿循环的必要条件来定义的。韧性是使用从图中删除的顶点数量与生成的连接组件数量的比率来定义的。很容易看出，具有哈密顿环的图是 1-韧的，但 Chvatal（1973）关于韧度大于某个常数的图将具有哈密顿环的猜想是该领域尚未解决的主要问题。在本研究中，我们考虑了当图类受到限制时的 Chvatal 猜想，并表明该猜想对于以图 2K_2 作为禁止归纳子图的图成立。我们还在继续考虑进一步放宽禁止的诱导子图的情况。图中包含的循环类型随着图中边数的增加而增加。长期以来，人们一直从极值问题的角度进行研究，以确定类型数量增加的趋势。在本研究中，我们将最小度条件视为给定图的条件，并且我们提出的结果改进了有关 k 个连续长度循环或 k 个连续长度循环的存在性（公差为 2）的现有结果。明白了。在证明中，我们没有直接考虑环，而是采用巧妙的归纳法来证明连接两个指定顶点的路径长度的结果，并得到作为一个系统的环的长度的结果。研究成果在2022年12月举行的应用数学联合研究会议上公布。 2023年2月，我们在庆应义塾大学召开了青年研究人员研究会议，与相关青年研究人员进行了信息交流和研究讨论。