５－２

助成番号 170149
研 究 成 果 報 告 書（国立情報学研究所の民間助成研究成果概要データベース・登録原稿）
研究テーマ（和文） ＡＢ

成分数指定の 2-因子問題に対する新手法の開発とその応用

研究テーマ（欧文） ＡＺ

A new approach for finding 2-factors with a prescribed number of components andits applications

研究氏
代表名者姓） チバ

ｶﾀｶﾅ ＣＣ名） シュウヤ

研究期間 Ｂ

２０１７～ ２０１８年

漢字 ＣＢ

千葉周也

報告年度 ＹR

２０１８年

ﾛｰﾏ字 ＣＺ

ChibaShuya

研究機関名

熊本大学

研究代表者 ＣＤ
所属機関・職名

熊本大学大学院先端科学研究部応用数理解析分野・准教授

概要 ＥＡ (600 字～800 字程度にまとめてください。)
本研究では、以下の３つの観点から成分数指定の 2-因子問題に対する新たな証明法の開発を目指した。
（１）2008 年に、Yamashita はハミルトン閉路の存在性に対する（連結度に依存した位数の）独立点集合内の 2 頂点次数和条件を与えることで、Chvatal-Erdos の定理（1972）を一般化した（Discrete Math.）。本研究では、この結果の成分数指定の 2-因子版への拡張について考察を行った。特に、「区間交換論法」と呼ばれる閉路上の区間と閉路に属さないグラフ上の道の置き換え操作に着目し、点素な閉路に区間交換論法を繰り返し適用することでその閉路を成分数指定の 2-因子まで拡張できることを示した。この手法によって、2-因子に対する「独立数と連結度の関係」、「独立点集合の平均次数」、「独立点集合内の 2 頂点次数和」に関する十分条件を与えることにも成功した。また、本研究成果
は Discrete Math.（2018）に掲載された。
（２）上記（１）で得られた証明法を利用することで、Ore（1960）による「非隣接 2 頂点次数和」に関する十分条件が指定した数のコード（閉路上の 2 頂点を結ぶ閉路上以外の辺）付き閉路へのグラフの分割の存在性を保証することを示し、1997 年の Brandt らの結果（J. Graph Theory）の改良に成功した。これにより、ある条件下では、上記証明法によって完全グラフの緩和構造への分割の存在性を保証できることが明らかになったので、グラフの染色数などの新たな応用可能性も見出すことができた。また、本研究成果は TGT30 などの国際会議に採択された。
（３）2000 年代初頭から現在までにかけて発表されてきた「点素な閉路の存在性に対する次数条件」の結果を調査することで、成分数指定の 2-因子、葉数を制限した全域木、有向ハミルトン閉路、指定した端点をもつ道因子の関係性について考察を行い、本研究の意味や重要性と 2-因子の応用可能性を明確にした。また、本研究成果は Graphs
Comb.（2018）に掲載された。

キーワード ＦＡ

2-因子

グラフの閉路分割

ハミルトン閉路（以下は記入しないでください。）
助成財団ｺｰﾄﾞ ＴＡ

研究課題番号 ＡＡ

研究機関番号 ＡＣ

シート番号- 1 -次数条件

発表文献（この研究を発表した雑誌・図書について記入してください。）
論文標題ＧＢ

Degree Conditions for the Existence of Vertex-Disjoint Cycles and Paths: A Survey

著者名 ＧＡ

Shuya Chiba,
Tomoki Yamashita

雑誌

ページ ＧＦ

1～83

雑誌名 ＧＣGraphs and Combinatorics

発行年 ＧＥ

2018

巻号 ＧＤ

34

論文標題ＧＢOn degree sum conditions for 2-factors with a prescribed number of cycles

著者名 ＧＡ

Shuya Chiba

雑誌

ページ ＧＦ2912～2918

雑誌名 ＧＣ

Discrete Mathematics

発行年 ＧＥ

28

巻号 ＧＤ

Partitioning a graph into cycles with a specified number of chords

著者名 ＧＡ

Shuya Chiba

ページ ＧＦ31341

雑誌名 ＧＣ

Proceedings of the 30th Workshop on Topological GraphTheory

発行年 ＧＥ

2018

巻号 ＧＤ

-

論文標題ＧＢ

Degree sum conditions for partitioning graphs into cycles with a specified number ofchords

著者名 ＧＡ

Shuya Chiba, Suyun
Jiang, Jin Yan

雑誌

1

論文標題ＧＢ
雑誌

0ページ ＧＦ

6

雑誌名 ＧＣ

Proceedings of the Engineering Workshop 2018 in Kumamoto(Mechanical System Engineering and Mathematics)

発行年 ＧＥ

2018

巻号 ＧＤ

-

著者名 ＨＡ
図書

書名 ＨＣ
出版者 ＨＢ発行年 ＨＤ

総ﾍﾟｰｼﾞ ＨＥ

欧文概要 ＥＺIn this research, we focused on the existence problem of a 2-factor with a prescribed number ofcomponents. In particular, we studied the difference and relationship between such a 2-factor and aHamilton cycle (i.e., a special case of a 2-factor with a prescribed number of components) and considered
a new approach for finding a 2-factor in terms of the following.
(1) In 2008, Yamashita gave a sufficient condition concerning the maximum value of the degree sums ofsome independent set for the existence of a Hamilton cycle and generalized a result of Chvatal-Erdos(1972) concerning the relationship between the connectivity, the independence number and thehamiltonicity. In this research, we generalized this result by considering replacements of intervals
on a cycle and paths which do not belong to the cycle.
(2) By using the technique in (1), we extended a result of Brandt et al. (J. Graph Theory, 1997) toa result on partitioning a graph into a prescribed number of cycles with a specified number of chords,
and we showed a difference between chorded cycles and complete subgraphs in terms of degree sum
conditions.
(3) We provided many results and conjectures by giving a survey on degree conditions for vertex-disjointcycles in graphs. In particular, we discovered relationships between results on 2-factors with aprescribed number of components, results on spanning trees with few leaves, results on directed Hamilton
cycles and results on path-factors.

- 2 -