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 条
  • [41] Token Sliding on Graphs of Girth Five
    Valentin Bartier
    Nicolas Bousquet
    Jihad Hanna
    Amer E. Mouawad
    Sebastian Siebertz
    Algorithmica, 2024, 86 : 638 - 655
  • [42] Cycles and Girth in Pebble Assignment Graphs
    Fiorini, E.
    Johnston, G.
    Lind, M.
    Woldar, A.
    Wong, T. W. H.
    GRAPHS AND COMBINATORICS, 2022, 38 (05)
  • [43] ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH
    Kayll, P. Mark
    Morris, Michael
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2023, 18 (02) : 234 - 243
  • [44] Topological minors in graphs of large girth
    Kühn, D
    Osthus, D
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 364 - 380
  • [45] The size of bipartite graphs with a given girth
    Hoory, S
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 215 - 220
  • [46] On Tensor Product of Graphs, Girth and Triangles
    Patil, H. P.
    Raja, V.
    IRANIAN JOURNAL OF MATHEMATICAL SCIENCES AND INFORMATICS, 2015, 10 (01): : 139 - 147
  • [47] Secret sharing on large girth graphs
    László Csirmaz
    Péter Ligeti
    Cryptography and Communications, 2019, 11 : 399 - 410
  • [48] The hub number, girth and Mycielski graphs
    Liu, Xiaoping
    Dang, Zhilan
    Wu, Baoyindureng
    INFORMATION PROCESSING LETTERS, 2014, 114 (10) : 561 - 563
  • [49] Cycles and Girth in Pebble Assignment Graphs
    E. Fiorini
    G. Johnston
    M. Lind
    A. Woldar
    T. W. H. Wong
    Graphs and Combinatorics, 2022, 38
  • [50] Secret sharing on large girth graphs
    Csirmaz, Laszlo
    Ligeti, Peter
    CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2019, 11 (03): : 399 - 410
12345