グラフのタフネス,平面性と次数を制限した全域木の関係

图的韧性、平坦度与有限度生成树的关系

• 批准号: 10J04633
• 负责人: 小関 健太
• 金额: $ 1.79万
• 依托单位: National Institute of Informatics
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10J04633/
• 关键词: グラフ; ハミルトン閉路; 平面グラフ; トーラス上のグラフ; タフネス; 全域閉歩道; k-木

論文2では当研究課題の目的の一つである,「トーラス上の任意の4-連結グラフはハミルトン閉路を持つ」というGrunbaum, Nash-Williams予想に関して,重要な部分的解決を与えている.Tutteの平面グラフの結果以降,閉曲面上のグラフのハミルトン性に関してさまざまな結果が示されてきたが,Grunbaum, Nash-Williamsの予想は40年以上前に予想された重要な未解決問題である.この予想の難しさの一因は,平面や射影平面上では現れなかった,トーラス上の4-連結グラフで「タフネスがちょうど1」であるものが存在する,という事実である.通常,ハミルトン閉路に関する問題は,帰納法を適用する都合上,「ハミルトン閉路を持つ」よりも強い性質を示す方が良い場合が多く,実際に平面・射影平面の結果は全てそのような手法で証明されている.しかし,そのようなより強い性質は「タフネスがちょうど1」であるグラフでは,少数の例外を除き,成り立たないことが示されているため,平面や射影平面では考慮する必要のない,「タフネスがちょうど1となるグラフ」が,既存の手法を適用するための障害となっていた.この点を考慮し,われわれは既存の研究とは根本的に異なる手法を提案することで,「トーラス上の任意の4・連結グラフは,タフネスがちょうど1ならば,ハミルトン閉路を持つ」という結果を示している.したがって,Grunbaum, Nash-Williams予想の解決のためには,タフネスが1でないグラフのみを考慮すれば良く,そこで平面や射影平面の場合に成功した既存の手法を用いることができる可能性がある.上記した以外にも,Grunbaum, Nash-Williams予想に関連して,本年度はいくつかの結果も得ている

Paper 2: In response to one of the objectives of the research project,"Any 4-link on the surface of a closed circuit", Grunbaum, Nash-Williams proposes a solution to the important part of the problem.Tutte's planar solution results in the reduction of the closed surface of a closed circuit. Nash-Williams thought about it more than 40 years ago. This is because the plane and the projection plane appear on the 4-link chain, and the 4-link chain exists. Usually, the closed circuit problem is closed, and the method of inclusion is applied. The closed circuit problem is closed, and the strong property is shown in many good cases. In fact, the result of the plane projection plane is completely proved by the method. A few exceptions are included in the list, and a few exceptions are included in the list. A plane is a projective plane, and a necessary part of the list is considered. The existing method is applied to the list. This point is taken into account, and the existing research and fundamental differences in methods are proposed. The results are shown in the following paragraphs: "Any link on the site 4. Link to the site." For example,Grunbaum, Nash-Williams thought about the possibility of success in the case of plane and projection plane. In addition to the above,Grunbaum, Nash-Williams wanted to be related, and this year, the results were achieved.

项目成果

4-connected projective-planar graphs are Hamiltonian-connected

• DOI: 10.1016/j.jctb.2014.11.006
• 发表时间: 2013-01
• 期刊: J. Comb. Theory B
• 作者: K. Kawarabayashi;K. Ozeki

A simpler proof for the two disjoint odd cycles theorem

• DOI: 10.1016/j.jctb.2012.11.004
• 发表时间: 2013-05
• 期刊: J. Comb. Theory B
• 作者: K. Kawarabayashi;K. Ozeki

{4,5} is not coverable : a counterexample to a conjecture of Kaiser and Skrekovski

{4,5} 不可覆盖：Kaiser 和 Skrekovski 猜想的反例

• DOI: 10.1137/120877817
• 发表时间: 2013
• 期刊: SIAM J. Discrete Math
• 作者: R. Cada;S. Chiba;K. Ozeki;P. Vrana;K. Yoshimoto
• 通讯作者: K. Yoshimoto

Hamilton cycles in 4-connected triangulations of the torus

哈密​​顿循环在环面的 4 连通三角剖分中

• 发表时间: 2011
• 作者: K.Kawarabayashi;K.Ozeki
• 通讯作者: K.Ozeki

A sufficient and necessary condition for the existence of a spanning tree with specified vertices having large degrees

具有大度指定顶点的生成树存在的充分必要条件

• 发表时间: 2013
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: Y. Egawa;K. Ozeki
• 通讯作者: K. Ozeki