５－２

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

グラフのハミルトン閉路に関する Nash-Williams と Grunbaum 予想の解決

研究テーマ（欧文） ＡＺ

Nash-Williams and Grunbaum conjecture related to Hamiltonian cycles in graphs

研
究氏
代表名
者

ｶﾀｶﾅ ＣＣ姓） オゼキ

名） ケンタ

研究期間 Ｂ

２０１４～ ２０１６

漢字 ＣＢ

小関健太

報告年度 ＹR２０１６年

ﾛｰﾏ字 ＣＺ OzekiKenta

研究機関名

国立情報学研究所

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

年

国立情報学研究所 ビッグデータ数理国際研究センター ・ 特任助教

概要 ＥＡ (600 字～800 字程度にまとめてください。)
本研究の目的は，40 年以上未解決でありグラフ理論全体の中でも重要な以下の予想の解決であった．
予想 (Grunbaum `70, Nash-Williams `73)
トーラス上の 4-連結グラフはハミルトン閉路を持つ．
残念ながら完全な解決を期間中に与えることはできなかったが，いくつかの重要な結果を示しており，それらを抜粋して報告する．
発表文献一つ目の ``5-connected toroidal graphs are Hamiltonian-connected’’ では「トーラス上の5-連結グラフはハミルトン連結である」という結果を示した．「ハミルトン連結」という性質は「ハミルトン閉路を持つ」という性質に類似しているが真に強いものである．特に，本研究では，既存の結果で使われている手法を改良することに成功し，この結果のみならず，さらなる発展が望めるものである．
他の二つの発表文献は，予想の対象を少し変更した場合に起こる現象を示している．
``A characterization of K_{2,4}-minor-free graphs’’ では，K_{2,4} をマイナーとして含まないグラフの完全な特徴付けを与えている．トーラスに埋め込めるグラフはいくつかのグラフをマイナーとして含まないもの，として特徴づけられるため，この観点からグラフの性質を調べたものである．この研究の系として「K_{2,4}-マイナーを持たない 3-連結グラフはハミルトン閉路を持つ」ことが示される．
``Decomposing plane cubic graphs’’では対象を 3-連結平面 3－正則グラフとし，特殊な性質を持つ木の存在性を示している．ここでの木の持つ性質は，ある意味でハミルトン性とは正反対のものであり，その差からハミルトン性が考察できる．
それら 3 本の論文以外でも，4 本の出版済論文・3 本の出版予定論文・15 本の投稿論文を得ている．

キーワード ＦＡトーラス

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

研究課題番号 ＡＡ

研究機関番号 ＡＣ

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

5-connected toroidal graphs are Hamiltonian-connected

著者名 ＧＡ

Kawarabayashi,Ozeki

雑誌名 ＧＣSIAM J. Discrete Math.

ページ ＧＦ112 ～ 140

発行年 ＧＥ

2雑誌

016

論文標題ＧＢA characterization of K_{2,4}-minor-free graphs

著者名 ＧＡ

Ellingham, Marshall,Ozeki, Tsuchiya

雑誌名 ＧＣSIAM J. Discrete Math.

ページ ＧＦ955 ～ 975

発行年 ＧＥ

2巻号 ＧＤ

30

巻号 ＧＤ

30

巻号 ＧＤ

52A

雑誌

論文標題ＧＢ

Decomposing plane cubic graphs

著者名 ＧＡ

Ozeki, Ye016

雑誌

ページ ＧＦ40 ～ 46

雑誌名 ＧＣ

European J. Combin.

発行年 ＧＥ2016

著者名 ＨＡ
図書

書名 ＨＣ
出版者 ＨＢ発行年 ＨＤ総ﾍﾟｰｼﾞ ＨＥ

発行年 ＨＤ

総ﾍﾟｰｼﾞ ＨＥ

著者名 ＨＡ
図書

書名 ＨＣ
出版者 ＨＢ

欧文概要 ＥＺThe purpose of this study is to solve the following conjecture, which is famous on graph theory.
Conjecture (Grunbaum `70, Nash-Williams `73)
Every 4-connected graph on the torus has a Hamiltonian cycle.
During the study, we gave several important results related to the conjecture. Here I introduce
some of them.
In the first paper ``5-connected toroidal graphs are Hamiltonian-connected’’ on the list, we provedthat Every 5-connected graph on the torus is Hamiltonian-connected. The property of being
Hamiltonian-connected is closely related to, but stronger than, that of being Hamiltonian. In thiswork, we improved a known method, called ``Tutte path’’. This improvement would be able to be used
to other works.
Other two papers considered situations that occur when we slightly change the targets.
The paper ``A characterization of K_{2,4}-minor-free graphs’’ gives a complete characterizationof graphs without K_{2,4} as a minor, Since it is known that graphs that can be embedded on the torus
are characterized as forbidden minors, we can see graphs on the torus from this direction. As a corollary,it is shown that every 3-connected graph without K_{2,4}-minor is Hamiltonian.
In the paper ``Decomposing plane cubic graphs’’, we focus on 3-connected 3-regular plane graphs
and showed the existence of a spanning tree with certain conditions, which is in some sense opposite
from Hamiltonian cycles. We can study the Hamiltonicity from the gap.
Except for those papers, we also gave four published papers, three accepted papers, and 15 submitted
papers.

- 2 -