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
相关论文
共 32 条
  • [1] Non-hamiltonian 1-tough triangulations with disjoint separating triangles
    Fujisawa, Jun
    Zamfirescu, Carol T.
    DISCRETE APPLIED MATHEMATICS, 2020, 284 (284) : 622 - 625
  • [3] On the number of hamiltonian cycles in triangulations with few separating triangles
    Brinkmann, Gunnar
    Souffriau, Jasper
    Van Cleemput, Nico
    JOURNAL OF GRAPH THEORY, 2018, 87 (02) : 164 - 175
  • [4] On the size of maximally non-hamiltonian digraphs
    Lichiardopol, Nicolas
    Zamfirescu, Carol T.
    ARS MATHEMATICA CONTEMPORANEA, 2019, 16 (01) : 59 - 66
  • [5] A Note on Long non-Hamiltonian Cycles in One Class of Digraphs
    Darbinyan, Samvel Kh.
    Karapetyan, Iskandar A.
    2013 COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES (CSIT), 2013,
  • [6] A Note on Long non-Hamiltonian Cycles in One Class of Digraphs
    Darbinyan, Samvel Kh.
    Karapetyan, Iskandar A.
    2013 COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES (CSIT), 2013,
  • [7] Non-Hamiltonian Graphs with Large Minimum Degree
    Fu, Lingting
    Gao, Liqing
    Wang, Jian
    Yang, Weihua
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2024, 47 (01)
  • [8] Each maximal planar graph with exactly two separating triangles is Hamiltonian
    Helden, Guido
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (14) : 1833 - 1836
  • [9] On longest non-Hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li
    Darbinyan, S. Kh.
    Karapetyan, I. A.
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 537 - 549
  • [10] Counting Hamiltonian cycles in planar triangulations
    Liu, Xiaonan
    Wang, Zhiyu
    Yu, Xingxing
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2022, 155 : 256 - 277