Regularity Lemmaの禁止部分グラフ条件への適用

将正则引理应用于禁止的子图条件

基本信息

批准号：
20J15332
负责人：
前澤俊一
金额：
$ 1.09万
依托单位：
Yokohama National University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-24 至 2022-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20J15332/
关键词：
Regularity Lemma 禁止部分グラフ条件密グラフ次数条件全域木

项目摘要

本研究の目的はRegularity Lemmaを禁止部分グラフ条件が課されたグラフに適用することである．目的達成のため，本研究では密なグラフや禁止部分グラフ条件の課されたグラフの構造解析をすることから始めた．そして，本研究に関係深い成果を5本の論文にまとめ，査読ありの国際誌に投稿した．そのうち3本が本年度にすでに受理されている．以下，本研究に関係する結果の詳細を記載する．1つ目の結果はグラフが与えられたkに対して超過数を制限した全域木をもつためのclosure型の次数条件に関する結果である．全域木の超過数は各頂点から出る辺の本数を制限した全域木の拡張研究である．そして，closure型の次数条件はOre型やFan型とよばれるいくつかの次数条件よりも弱い条件である．以上のことから本研究は概念としての拡張性，条件として弱さから非常に有用な結果といえる．本研究結果は国際誌Graphs and Combinatoricsに受理されている．2つ目の結果はグラフがk-leaf-connectedであるための次数条件に関する結果である．k-leaf-connectedという概念はハミルトン連結とよばれる巡回セールスマン問題とも深遠な関係にある概念の拡張である．本研究では既存の次数条件よりも弱い次数条件でグラフがk-leaf-connectedであることが保証できることを示した．本研究結果は国際誌Discrete Mathematicsに受理されている．3つ目はグラフが全域k-treeをもつための禁止部分グラフ条件に関する結果である．これは2010年に太田・杉山によってなされた全域k-treeをもつための禁止部分グラフペアの予想を肯定的に解決したものである．

这项研究的目的是将规律性引理应用于施加禁止子图条件的图。为了实现目标，这项研究首先是对图形的结构分析，这些图形受到密集图和禁止的子图条件。与这项研究特别相关的结果已汇编为五篇论文，并提交给具有同行评审的国际期刊。其中三个已经被今年接受。描述了与本研究相关的结果的以下细节。第一个结果是闭合类型的订单条件的结果，该图具有具有给定k的超限量的生成树。跨越树的过量是对跨越树木的扩展研究，该研究限制了每个顶点从每个顶点出现的边缘数量。闭合类型的顺序条件比某些称为矿石类型和风扇类型的顺序条件弱。从以上来看，这项研究是一个非常有用的结果，因为它作为概念和弱点作为条件。这项研究的结果已在国际期刊图和组合学中接受。第二个结果是该图与k叶连接的顺序条件的结果。 K叶连接的概念是该概念的扩展，该概念也与称为汉密尔顿连接的旅行推销员问题密切相关。这项研究表明，可以保证该图在较弱的订单条件下与现有订单条件相比是在较弱的订单条件下与之相连的。这项研究的结果已在国际杂志离散数学中接受。第三个是该图具有全区域K树的禁止子图条件的结果。这是对OTA和Sugiyama在2010年因拥有全范围K-Tree而在2010年对禁止的子图对的预测的积极解决方案。