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 条
  • [41] The Game Coloring Number of Planar Graphs with a Specific Girth
    Keaitsuda Maneeruk Nakprasit
    Kittikorn Nakprasit
    Graphs and Combinatorics, 2018, 34 : 349 - 354
  • [42] Injective (Δ+1)-coloring of planar graphs with girth 6
    Borodin, O. V.
    Ivanova, A. O.
    SIBERIAN MATHEMATICAL JOURNAL, 2011, 52 (01) : 23 - 29
  • [43] Path partition of planar graphs with girth at least six
    Liu, Xiaoling
    Sun, Lei
    Zheng, Wei
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (07)
  • [44] Acyclic chromatic indices of planar graphs with large girth
    Wang, Weifan
    Shu, Qiaojun
    Wang, Kan
    Wang, Ping
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) : 1239 - 1253
  • [45] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Mengjiao Rao
    Jianfeng Hou
    Qinghou Zeng
    Graphs and Combinatorics, 2022, 38
  • [46] Subcubic planar graphs of girth 7 are class I
    Bonduelle, Sebastien
    Kardos, Frantisek
    DISCRETE MATHEMATICS, 2022, 345 (10)
  • [47] Injective choosability of subcubic planar graphs with girth 6
    Brimkov, Boris
    Edmond, Jennifer
    Lazar, Robert
    Lidicky, Bernard
    Messerschmidt, Kacy
    Walker, Shanise
    DISCRETE MATHEMATICS, 2017, 340 (10) : 2538 - 2549
  • [48] Injective (Δ + 1)-coloring of planar graphs with girth 6
    O. V. Borodin
    A. O. Ivanova
    Siberian Mathematical Journal, 2011, 52 : 23 - 29
  • [49] The game coloring number of planar graphs with a given girth
    Sekiguchi, Yosuke
    DISCRETE MATHEMATICS, 2014, 330 : 11 - 16
  • [50] The Game Coloring Number of Planar Graphs with a Specific Girth
    Nakprasit, Keaitsuda Maneeruk
    Nakprasit, Kittikorn
    GRAPHS AND COMBINATORICS, 2018, 34 (02) : 349 - 354
12345