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

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

• 批准号: 20K03720
• 负责人: 千葉 周也
• 金额: $ 2.91万
• 依托单位: Kumamoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K03720/
• 关键词: 有向閉路詰込み; ハミルトン閉路; 次数条件; 禁止部分グラフ条件; 有向閉路分割; 有向道分割; グラフ理論; 有向グラフ; 二部グラフ; グラフの詰込み; グラフの分割

(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)Number of times specified in the order."Specify the number of times, specify the number of times." The results of this research are related to the closed circuit problem. The results of Brandt in 1997 (J. Graph Theory) and Chiba-Yamashita in 2018 (SIAM J. Discrete Math.) Common problems arise in the development of new methods and knowledge. (2)A detailed review of existing research results related to the generalization of closed-circuit problems and the degree of connectivity of independent numbers of directional closed-circuit segmentation problems. The concept of closed circuit includes the concept of "intersecting cycle" and the concept of "closed circuit". The concept of closed circuit includes the concept of "intersecting cycle" and the concept of "closed circuit". The concept of "closed circuit" includes the concept of "closed circuit" and the concept of "closed circuit". 2022). The research results of the company were reported. (3)J. Combin.(Electron. J. Combin., 1999). The division problem and the correlation problem are discussed in detail. The conditions for the division problem and the correlation problem are discussed. 2022 & Graphs Combin., 2023). The research results of the company were reported.

项目成果

Induced nets and Hamiltonicity of claw-free graphs

无爪图的诱导网和哈密顿度

• DOI: 10.1007/s00373-020-02265-7
• 发表时间: 2021
• 期刊: Graphs and Combinatorics
• 影响因子: 0.7
• 作者: S. Chiba;J. Fujisawa
• 通讯作者: J. Fujisawa

On degree sum conditions for directed path-factors with a specified number of paths

关于具有指定路径数的有向路径因子的度和条件

• DOI: 10.1016/j.disc.2020.112114
• 发表时间: 2020
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: Shuya Chiba;Eishi Mishio;Pierre Montalbano
• 通讯作者: Pierre Montalbano

Spanning Bipartite Graphs with Large Degree Sum in Graphs of Odd Order

奇数阶图中具有大度和的生成二部图

• DOI: 10.1007/s00373-021-02349-y
• 发表时间: 2021
• 期刊: Graphs and Combinatorics
• 影响因子: 0.7
• 作者: Chiba Shuya;Saito Akira;Tsugaki Masao;Yamashita Tomoki
• 通讯作者: Yamashita Tomoki

Minimum Number of Edges Guaranteeing the Existence of a $K_{1, t}$-Factor in a Graph

保证图中 $K_{1, t}$ 因子存在的最小边数

• DOI: 10.1007/s00373-023-02616-0
• 发表时间: 2023
• 期刊: Graphs and Combinatorics
• 影响因子: 0.7
• 作者: Shuya Chiba;Yoshimi Egawa;Shinya Fujita
• 通讯作者: Shinya Fujita

Polytech Clermont-Ferrand(フランス)

克莱蒙费朗理工学院（法国）