Non-hamiltonian triangulations with distant separating triangles

被引:2
作者
Ozeki, Kenta [1 ]
Zamfirescu, Carol T. [2 ]
机构
[1] Yokohama Natl Univ, Fac Environm & Informat Sci, Hodogaya Ku, 79-2 Tokiwadai, Yokohama, Kanagawa 2408501, Japan
[2] Univ Ghent, Dept Appl Math Comp Sci & Stat, Krijgslaan 281-S9, B-9000 Ghent, Belgium
关键词
Triangulation; Separating triangle; Non-hamiltonian; PLANE TRIANGULATIONS; GRAPHS; CYCLES;
D O I
10.1016/j.disc.2018.03.018
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In 1996 Bohme, Harant, and Tkac asked whether there exists a non-hamiltonian triangulation with the property that any two of its separating triangles lie at distance at least 1. Two years later, Bohme and Harant answered this in the affirmative, showing that for any non-negative integer d there exists a non-hamiltonian triangulation with seven separating triangles every two of which lie at distance at least d. In this note we prove that the result holds if we replace seven with six, remarking that no non-hamiltonian triangulation with fewer than six separating triangles is known. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:1900 / 1902
页数:3
相关论文
共 33 条
[21]   Non-separating subgraphs in highly connected graphs [J].
Fujita, Shinya ;
Kawarabayashi, Ken-ichi .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 117 :1-21
[22]   Cycle double covers and non-separating cycles [J].
Hoffmann-Ostenhof, Arthur ;
Zhang, Cun-Quan ;
Zhang, Zhang .
EUROPEAN JOURNAL OF COMBINATORICS, 2019, 81 :276-284
[23]   Non-equivalent partitions of d-triangles with Steiner points [J].
Plaza, A ;
Suárez, JP ;
Padrón, MA .
APPLIED NUMERICAL MATHEMATICS, 2004, 49 (3-4) :415-430
[24]   Strong Embeddings of Outer Planar Near-triangulations on Non-orientable Surfaces [J].
刘同印 ;
刘彦佩 ;
任韩 .
Northeastern Mathematical Journal, 2000, (02) :225-232
[25]   Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models [J].
Chris D. Bartels ;
Jeff A. Bilmes .
Machine Learning, 2011, 84 :249-289
[26]   Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models [J].
Bartels, Chris D. ;
Bilmes, Jeff A. .
MACHINE LEARNING, 2011, 84 (03) :249-289
[27]   Non-separating subgraphs after deleting many disjoint paths [J].
Kawarabayashi, Ken-ichi ;
Ozeki, Kenta .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (01) :54-59
[28]   Non-separating cycles and 5-cycle double covers [J].
Li, Xiaoyu ;
Hao, Rong-Xia ;
Luo, Rong ;
Zhang, Cun-Quan .
DISCRETE MATHEMATICS, 2025, 348 (09)
[29]   Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers [J].
Erickson, Jeff ;
Nayyeri, Amir .
PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2011, :1166-1176
[30]   Solving Hamiltonian Cycle by an EPT algorithm for a non-sparse parameter [J].
Saether, Sigve Hortemo .
DISCRETE APPLIED MATHEMATICS, 2017, 228 :88-97