Counting Hamiltonian cycles in planar triangulations

被引：2
作者：
Liu, Xiaonan [1 ]
Wang, Zhiyu [1 ]
Yu, Xingxing [1 ]
机构：
[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
来源：
JOURNAL OF COMBINATORIAL THEORY SERIES B | 2022年 / 155卷
关键词：
Hamiltonian cycles; Planar triangulations; Tutte paths; Tutte cycles; MAXIMUM NUMBER; GRAPHS; PATHS;
D O I：
10.1016/j.jctb.2022.02.008
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Hakimi, Schmeichel, and Thomassen (1979) [10] conjectured that every 4-connected planar triangulation G on n vertices has at least 2(n - 2)(n - 4) Hamiltonian cycles, with equality if and only if G is a double wheel. In this paper, we show that every 4-connected planar triangulation on n vertices has omega(n(2)) Hamiltonian cycles. Moreover, we show that if G is a 4-connected planar triangulation on n vertices and the distance between any two vertices of degree 4 in G is at least 3, then G has 2(omega(n1/4)) Hamiltonian cycles. (C)& nbsp;2022 Elsevier Inc. All rights reserved.
引用
收藏
页码：256 / 277
页数：22
相关论文
共 21 条
  • [1] Cycles in 5-connected triangulations
    Alahmadi, A.
    Aldred, R. E. L.
    Thomassen, C.
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 140 : 27 - 44
  • [2] The minimum number of minimal codewords in an [n, k]-code and in graphic codes
    Alahmadi, A.
    Aldred, R. E. L.
    de la Cruz, R.
    Ok, S.
    Sole, P.
    Thomassen, C.
    [J]. DISCRETE APPLIED MATHEMATICS, 2015, 184 : 32 - 39
  • [3] The maximum number of minimal codewords in an [n, k]-code
    Alahmadi, A.
    Aldred, R. E. L.
    de la Cruz, R.
    Sole, P.
    Thomassen, C.
    [J]. DISCRETE MATHEMATICS, 2013, 313 (15) : 1569 - 1574
  • [4] The maximum number of minimal codewords in long codes
    Alahmadi, A.
    Aldred, R. E. L.
    dela Cruz, R.
    Sole, P.
    Thomassen, C.
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (03) : 424 - 429
  • [5] Altshuler A., 1972, DISCRETE MATH, V1, P299, DOI DOI 10.1016/0012-365X(72)90037-4
  • [6] Böhme T, 1999, J GRAPH THEOR, V32, P81
  • [7] 4-connected polyhedra have at least a linear number of hamiltonian cycles
    Brinkmann, Gunnar
    Van Cleemput, Nico
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2021, 97
  • [8] On the number of hamiltonian cycles in triangulations with few separating triangles
    Brinkmann, Gunnar
    Souffriau, Jasper
    Van Cleemput, Nico
    [J]. JOURNAL OF GRAPH THEORY, 2018, 87 (02) : 164 - 175
  • [9] HAMILTONICITY OF 5-CONNECTED TOROIDAL TRIANGULATIONS
    BRUNET, R
    RICHTER, RB
    [J]. JOURNAL OF GRAPH THEORY, 1995, 20 (03) : 267 - 286
  • [10] NUMBER OF HAMILTONIAN CYCLES IN A MAXIMAL PLANAR GRAPH
    HAKIMI, SL
    SCHMEICHEL, EF
    THOMASSEN, C
    [J]. JOURNAL OF GRAPH THEORY, 1979, 3 (04) : 365 - 370
123