有向グラフ上の詰込み・分割問題に対する新手法の開発とその応用

开发有向图填充和划分问题的新方法和应用

基本信息

批准号：
20K03720
负责人：
千葉周也
金额：
$ 2.91万
依托单位：
Kumamoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

(1) 指定された個数からなる指定された長さの有向閉路詰込みに対する次数条件1984年にEl-Zaharによって提起された「指定された個数からなる指定された長さの閉路分割」に対する次数条件を有向グラフ版へと拡張する方法について検討することで、「指定された個数からなる指定された奇数長の有向閉路詰め込み」に対する最良な次数条件を、前年度までに定めていた方針によって実際に与えることに成功した。本研究成果は、閉路詰込み問題に関する1997年のBrandtらの結果（J. Graph Theory）および2018年のChiba-Yamashitaの結果（SIAM J. Discrete Math.）の共通の一般化となるものであり、詰込み問題に対する新手法の開発において新たな知見を見出したといえる。(2) ハミルトン閉路の一般化およびグラフの連結度と独立数有向閉路分割問題に対する新たな研究の方向性を模索するために、無向グラフ上のハミルトン閉路問題に関する既存の研究成果の精査を行なった。特に、ハミルトン閉路や辺支配閉路、指定された頂点を通る閉路など、閉路に関する多くの概念を包括する“intersecting cycle”と呼ばれる新しい閉路の概念を導入し、その閉路の存在性に対するグラフの連結度と独立数の関係を明らかにし、学術雑誌（Discrete Math., 2022）を通してその研究成果を発表した。(3) グラフの分割問題および関連問題における十分条件グラフ上の閉路分割数・道分割数に対する禁止部分グラフ条件や星グラフの族の分割に対するグラフの最小次数とサイズに関する条件等について考察し、学術雑誌（Electron. J. Combin., 2022 & Graphs Combin., 2023）を通してその研究成果を発表した。

(1)由指定数量组成的指定长度的有向循环打包的排序条件有向图通过考虑如何扩展到免费版本，我们实际上按照前一年制定的政策，提供了“由指定件数组成的指定奇数长度的定向循环包装”的最佳订购条件，这是非常成功的。。该研究结果是Brandt等人1997年的结果（J. Graph Theory）和Chiba-Yamashita 2018年的结果（SIAM J. Discrete Math.）关于循环填充问题的共同概括，可以说：在开发解决填充问题的新方法时发现了新知识。（2）为了推广哈密顿循环，探索图连通性和独立有向循环划分问题的新研究方向，我们将检验现有关于无向图哈密顿循环问题的研究成果。特别是，我们引入了一个新的循环概念，称为“相交循环”，它包含许多与循环相关的概念，例如哈密顿循环、边支配循环和穿过指定顶点的循环，并且我们介绍了基于图的连通度他阐明了循环的存在性。他阐明了与独立数之间的关系，并在学术期刊上发表了他的研究成果（Discrete Math., 2022）。 (3)图划分问题及相关问题的充分条件我们考虑图上循环划分和路径划分的数量的禁止子图条件，以及关于划分星图族的图的最小度和大小的条件，以及研究结果发表在杂志上（Electron. J. Combin., 2022 & Graphs Combin., 2023）。