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 条
  • [1] Infinitely Many Hypohamiltonian Cubic Graphs of Girth 7
    Edita Máčajová
    Martin Škoviera
    Graphs and Combinatorics, 2011, 27 : 231 - 241
  • [2] Planar Hypohamiltonian Graphs on 40 Vertices
    Jooyandeh, Mohammadreza
    McKay, Brendan D.
    Ostergard, Patric R. J.
    Pettersson, Ville H.
    Zamfirescu, Carol T.
    JOURNAL OF GRAPH THEORY, 2017, 84 (02) : 121 - 133
  • [3] Infinitely Many Hypohamiltonian Cubic Graphs of Girth 7
    Macajova, Edita
    Skoviera, Martin
    GRAPHS AND COMBINATORICS, 2011, 27 (02) : 231 - 241
  • [4] On Planar Hypohamiltonian Graphs
    Wiener, Gabor
    Araya, Makoto
    JOURNAL OF GRAPH THEORY, 2011, 67 (01) : 55 - 68
  • [5] Injective coloring of planar graphs with girth 5
    Yuehua Bu
    Piaopiao Ye
    Frontiers of Mathematics in China, 2022, 17 : 473 - 484
  • [6] Injective coloring of planar graphs with girth 5
    Bu, Yuehua
    Yang, Qiang
    Zhu, Junlei
    Zhu, Hongguo
    AIMS MATHEMATICS, 2023, 8 (07): : 17081 - 17090
  • [7] Injective coloring of planar graphs with girth 5
    Bu, Yuehua
    Ye, Piaopiao
    FRONTIERS OF MATHEMATICS IN CHINA, 2022, 17 (03) : 473 - 484
  • [8] An Infinite Family of Planar Hypohamiltonian Oriented Graphs
    van Aardt, Susan A.
    Burger, Alewyn P.
    Frick, Marietjie
    GRAPHS AND COMBINATORICS, 2013, 29 (04) : 729 - 733
  • [9] An Infinite Family of Planar Hypohamiltonian Oriented Graphs
    Susan A. van Aardt
    Alewyn P. Burger
    Marietjie Frick
    Graphs and Combinatorics, 2013, 29 : 729 - 733
  • [10] 2-Distance coloring of planar graphs with girth 5
    Dong, Wei
    Xu, Baogang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (04) : 1302 - 1322
12345