Non-hamiltonian 1-tough triangulations with disjoint separating triangles

被引：0

作者：

Fujisawa, Jun ^{[1
]}

Zamfirescu, Carol T. ^{[2
,3
]}

机构：

[1] Keio Univ, Fac Business & Commerce, Kohoku Ku, Hiyoshi 4-1-1, Yokohama, Kanagawa 2238521, Japan

[2] Univ Ghent, Dept Appl Math Comp Sci & Stat, Krijgslaan 281,S9, B-9000 Ghent, Belgium

[3] Babes Bolyai Univ, Dept Math, Cluj Napoca, Romania

来源：

DISCRETE APPLIED MATHEMATICS | 2020年 / 284卷 / 284期

基金：

日本学术振兴会;

关键词：

Triangulation; Separating triangle; Non-hamiltonian; 1-tough; SHORTNESS EXPONENT; PLANAR; CYCLES;

D O I：

10.1016/j.dam.2020.03.053

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this note, we consider triangulations of the plane. Ozeki and the second author asked whether there are non-hamiltonian 1-tough triangulations in which every two separating triangles are disjoint. We answer this question in the affirmative and strengthen a result of Nishizeki by proving that there are infinitely many non-hamiltonian 1-tough triangulations with pairwise disjoint separating triangles. (C) 2020 Elsevier B.V. All rights reserved.

引用

页码：622 / 625

页数：4

共 10 条

[1] On Hamiltonian cycles in 4- and 5-connected plane triangulations
Bohme, T
Harant, J
[J]. DISCRETE MATHEMATICS, 1998, 191 (1-3) : 25 - 30
[2] Bohme T., 1996, TATRA MOUNTAINS MATH, V9, P97
[3] Brinkmann G, 2019, ELECTRON J COMB, V26
[4] Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6
[5] AN UPPER BOUND ON THE SHORTNESS EXPONENT OF 1-TOUGH, MAXIMAL PLANAR GRAPHS
DILLENCOURT, MB
[J]. DISCRETE MATHEMATICS, 1991, 90 (01) : 93 - 97
[6] Hamilton cycles in plane triangulations
Jackson, B
Yu, XX
[J]. JOURNAL OF GRAPH THEORY, 2002, 41 (02) : 138 - 150
[7] A 1-TOUGH NON-HAMILTONIAN MAXIMAL PLANAR GRAPH
NISHIZEKI, T
[J]. DISCRETE MATHEMATICS, 1980, 30 (03) : 305 - 307
[8] Non-hamiltonian triangulations with distant separating triangles
Ozeki, Kenta
Zamfirescu, Carol T.
[J]. DISCRETE MATHEMATICS, 2018, 341 (07) : 1900 - 1902
[9] 4-CONNECTED PROJECTIVE-PLANAR GRAPHS ARE HAMILTONIAN
THOMAS, R
YU, XX
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (01) : 114 - 132
[10] Tkac M, 1996, DISCRETE MATH, V154, P321

← 1 →