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 条
  • [1] Infinitely Many Hypohamiltonian Cubic Graphs of Girth 7
    Edita Máčajová
    Martin Škoviera
    Graphs and Combinatorics, 2011, 27 : 231 - 241
  • [2] Infinitely many planar cubic hypohamiltonian graphs of girth 5
    Goedgebeur, Jan
    Zamfirescu, Carol T.
    JOURNAL OF GRAPH THEORY, 2018, 88 (01) : 40 - 45
  • [3] Hypohamiltonian Planar Cubic Graphs with Girth 5
    McKay, Brendan D.
    JOURNAL OF GRAPH THEORY, 2017, 85 (01) : 7 - 11
  • [4] Circular edge-colorings of cubic graphs with girth six
    Kral, Daniel
    Macajova, Edita
    Mazak, Jan
    Sereni, Jean-Sebastien
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (04) : 351 - 358
  • [5] Generation of Cubic Graphs and Snarks with Large Girth
    Brinkmann, Gunnar
    Goedgebeur, Jan
    JOURNAL OF GRAPH THEORY, 2017, 86 (02) : 255 - 272
  • [6] Symmetric cubic graphs of small girth
    Conder, Marston
    Nedela, Roman
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (05) : 757 - 768
  • [7] A complete classification of cubic symmetric graphs of girth 6
    Kutnar, Klavdija
    Marusic, Dragan
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (01) : 162 - 184
  • [8] Domination and total domination in cubic graphs of large girth
    Dantas, Simone
    Joos, Felix
    Loewenstein, Christian
    Machado, Deiwison S.
    Rautenbach, Dieter
    DISCRETE APPLIED MATHEMATICS, 2014, 174 : 128 - 132
  • [9] Improved bounds for hypohamiltonian graphs
    Goedgebeur, Jan
    Zamfirescu, Carol T.
    ARS MATHEMATICA CONTEMPORANEA, 2017, 13 (02) : 235 - 257
  • [10] CUBIC CAYLEY GRAPHS OF GIRTH AT MOST 6 AND THEIR HAMILTONICITY
    Aboomahigir, E.
    Nedela, R.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (02): : 351 - 359
12345