Infinitely Many Hypohamiltonian Cubic Graphs of Girth 7

被引：10
|
作者：
Macajova, Edita [1 ]
Skoviera, Martin [1 ]
机构：
[1] Comenius Univ, Dept Comp Sci, Fac Math Phys & Informat, Bratislava 84248, Slovakia
来源：
GRAPHS AND COMBINATORICS | 2011年 / 27卷 / 02期
关键词：
Hypohamiltonian; Girth; Cubic graph; SNARKS;
D O I：
10.1007/s00373-010-0968-z
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The trivalent Coxeter graph of order 28 is the only known hypohamiltonian cubic graph of girth 7. In this paper we will construct an infinite family of hypohamiltonian cubic graphs of girth 7 and cyclic connectivity 6. The existence of cyclically 7-edge-connected hypohamiltonian cubic graphs other than the Coxeter graph, however, remains open.
引用
收藏
页码：231 / 241
页数：11
相关论文
共 50 条
  • [31] Superconnectivity of graphs with odd girth g and even girth h
    Balbuena, C.
    Garcia-Vazquez, P.
    Montejano, L. P.
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (2-3) : 91 - 99
  • [32] Extremal Graphs with Girth Nine
    Zhang Rui
    Sun Yongqi
    Wu Yali
    ARS COMBINATORIA, 2019, 142 : 345 - 356
  • [33] On the Girth of Random Cayley Graphs
    Gamburd, A.
    Hoory, S.
    Shahshahani, M.
    Shalev, A.
    Virag, B.
    RANDOM STRUCTURES & ALGORITHMS, 2009, 35 (01) : 100 - 117
  • [34] Girth and Total Domination in Graphs
    Henning, Michael A.
    Yeo, Anders
    GRAPHS AND COMBINATORICS, 2012, 28 (02) : 199 - 214
  • [35] Proximity, remoteness and girth in graphs
    Aouchiche, M.
    Hansen, P.
    DISCRETE APPLIED MATHEMATICS, 2017, 222 : 31 - 39
  • [36] Highly-connected planar cubic graphs with few or many Hamilton cycles
    Pivotto, Irene
    Royle, Gordon
    DISCRETE MATHEMATICS, 2019, 342 (12)
  • [37] All tight descriptions of 3-paths in plane graphs with girth at least 7
    Borodin, O. V.
    Ivanova, A. O.
    DISCRETE MATHEMATICS, 2021, 344 (05)
  • [38] On the girth of Hamiltonian weakly pancyclic graphs
    Bollobas, B
    Thomason, A
    JOURNAL OF GRAPH THEORY, 1997, 26 (03) : 165 - 173
  • [39] Domination in Graphs of Minimum Degree at least Two and Large Girth
    Christian Löwenstein
    Dieter Rautenbach
    Graphs and Combinatorics, 2008, 24 : 37 - 46
  • [40] Token Sliding on Graphs of Girth Five
    Bartier, Valentin
    Bousquet, Nicolas
    Hanna, Jihad
    Mouawad, Amer E.
    Siebertz, Sebastian
    ALGORITHMICA, 2024, 86 (02) : 638 - 655
12345