Hypohamiltonian Planar Cubic Graphs with Girth 5

被引：7
|
作者：
McKay, Brendan D. [1 ]
机构：
[1] Australian Natl Univ, Canberra, ACT, Australia
来源：
JOURNAL OF GRAPH THEORY | 2017年 / 85卷 / 01期
关键词：
graph generation; hypohamiltonian graph; planar graph; cubic graph; HYPOTRACEABLE GRAPHS;
D O I：
10.1002/jgt.22043
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4-cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices. (C) 2016 Wiley Periodicals, Inc.
引用
收藏
页码：7 / 11
页数：5
相关论文
共 50 条
  • [21] Flexibility of planar graphs of girth at least six
    Dvorak, Zdenek
    Masarik, Tomas
    Musilek, Jan
    Pangrac, Ondrej
    JOURNAL OF GRAPH THEORY, 2020, 95 (03) : 457 - 466
  • [22] Circular choosability of planar graphs with large girth
    Wang, Guanghui
    Liu, Guizhen
    ARS COMBINATORIA, 2011, 99 : 65 - 73
  • [23] Linear coloring of planar graphs with large girth
    Raspaud, Andre
    Wang, Weifan
    DISCRETE MATHEMATICS, 2009, 309 (18) : 5678 - 5686
  • [24] RECOLORING PLANAR GRAPHS OF GIRTH AT LEAST FIVE
    Bartier, Valentin
    Bousquet, Nicolas
    Feghali, Carl
    Heinrich, Marc
    Moore, Benjamin
    Pierron, Theo
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (01) : 332 - 350
  • [25] On linear coloring of planar graphs with small girth
    Dong, Wei
    Lin, Wensong
    DISCRETE APPLIED MATHEMATICS, 2014, 173 : 35 - 44
  • [26] FRACTIONAL COLORING OF PLANAR GRAPHS OF GIRTH FIVE
    Dvorak, Zdenek
    Hu, Xiaolan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (01) : 538 - 555
  • [27] An (F3, F5)-partition of planar graphs with girth at least 5
    Chen, Min
    Raspaud, Andre
    Wang, Weifan
    Yu, Weiqiang
    DISCRETE MATHEMATICS, 2023, 346 (02)
  • [28] Decomposing planar cubic graphs
    Hoffmann-Ostenhof, Arthur
    Kaiser, Tomas
    Ozeki, Kenta
    JOURNAL OF GRAPH THEORY, 2018, 88 (04) : 631 - 640
  • [29] Random cubic planar graphs
    Bodirsky, Manuel
    Kang, Mihyun
    Loeffler, Mike
    McDiarmid, Colin
    RANDOM STRUCTURES & ALGORITHMS, 2007, 30 (1-2) : 78 - 94
  • [30] 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