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 条
  • [31] Cubic vertex-transitive graphs of girth six
    Potacnik, Primoz
    Vidali, Janos
    DISCRETE MATHEMATICS, 2022, 345 (03)
  • [32] 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
  • [33] 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
  • [34] Hypohamiltonian graphs and their crossing number
    Zamfirescu, Carol T.
    ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (04):
  • [35] An oriented coloring of planar graphs with girth at least five
    Pinlou, Alexandre
    DISCRETE MATHEMATICS, 2009, 309 (08) : 2108 - 2118
  • [36] Labeling planar graphs with conditions on girth and distance two
    Wang, WF
    Lih, KW
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 17 (02) : 264 - 275
  • [37] Acyclic edge coloring of planar graphs with large girth
    Yu, Dongxiao
    Hou, Jianfeng
    Liu, Guizhen
    Liu, Bin
    Xu, Lan
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (47-49) : 5196 - 5200
  • [38] Choosability of the square of planar subcubic graphs with large girth
    Havet, F.
    DISCRETE MATHEMATICS, 2009, 309 (11) : 3553 - 3563
  • [39] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Rao, Mengjiao
    Hou, Jianfeng
    Zeng, Qinghou
    GRAPHS AND COMBINATORICS, 2022, 38 (04)
  • [40] FORBIDDEN CONFIGURATIONS FOR HYPOHAMILTONIAN GRAPHS
    Fabrici, Igor
    Madaras, Tomas
    Timkova, Maria
    OPUSCULA MATHEMATICA, 2018, 38 (03) : 357 - 377
12345