Hamiltonicity in connected regular graphs

被引：4
作者：
Cranston, Daniel W. [1 ]
Suil, O. [2 ]
机构：
[1] Virginia Commonwealth Univ, Dept Math & Appl Math, Richmond, VA 23284 USA
[2] Coll William & Mary, Dept Math, Williamsburg, VA 23185 USA
来源：
INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 22-24期
关键词：
Combinatorial problems; Hamiltonicity; Regular graphs; CYCLES;
D O I：
10.1016/j.ipl.2013.08.005
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In 1980, Jackson proved that every 2-connected k-regular graph with at most 3k vertices is Hamiltonian. This result has been extended in several papers. In this note, we determine the minimum number of vertices in a connected k-regular graph that is not Hamiltonian, and we also solve the analogous problem for Hamiltonian paths. Further, we characterize the smallest connected k-regular graphs without a Hamiltonian cycle. Published by Elsevier B.V.
引用
收藏
页码：858 / 860
页数：3
相关论文
共 50 条
  • [41] Hamiltonicity and pancyclicity of cartesian products of graphs
    Cada, Roman
    Flandrin, Evelyne
    Li, Hao
    DISCRETE MATHEMATICS, 2009, 309 (22) : 6337 - 6343
  • [42] Hamiltonicity of planar graphs with a forbidden minor
    Ellingham, M. N.
    Marshall, Emily A.
    Ozeki, Kenta
    Tsuchiya, Shoichi
    JOURNAL OF GRAPH THEORY, 2019, 90 (04) : 459 - 483
  • [43] Degree and neighborhood conditions for hamiltonicity of claw-free graphs
    Chen, Zhi-Hong
    DISCRETE MATHEMATICS, 2017, 340 (12) : 3104 - 3115
  • [44] ON THE RESILIENCE OF HAMILTONICITY AND OPTIMAL PACKING OF HAMILTON CYCLES IN RANDOM GRAPHS
    Ben-Shimon, Sonny
    Krivelevich, Michael
    Sudakov, Benny
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (03) : 1176 - 1193
  • [45] Conditional Edge-Fault Hamiltonicity of Cartesian Product Graphs
    Cheng, Chia-Wen
    Lee, Chia-Wei
    Hsieh, Sun-Yuan
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2013, 24 (10) : 1951 - 1960
  • [46] Vertex partitions of non-complete graphs into connected monochromatic k-regular graphs
    Sarkoezy, Gabor N.
    Selkow, Stanley M.
    Song, Fei
    DISCRETE MATHEMATICS, 2011, 311 (18-19) : 2079 - 2084
  • [47] Sharp thresholds for Hamiltonicity in random intersection graphs
    Efthymiou, Charilaos
    Spirakis, Paul G.
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) : 3714 - 3730
  • [48] A sufficient condition for Hamiltonicity in locally finite graphs
    Heuer, Karl
    EUROPEAN JOURNAL OF COMBINATORICS, 2015, 45 : 97 - 114
  • [49] Hamiltonicity of edge-chromatic critical graphs
    Cao, Yan
    Chen, Guantao
    Jiang, Suyun
    Liu, Huiqing
    Lu, Fuliang
    DISCRETE MATHEMATICS, 2020, 343 (07)
  • [50] Hamiltonicity in random directed graphs is born resilient
    Montgomery, Richard
    COMBINATORICS PROBABILITY & COMPUTING, 2020, 29 (06) : 900 - 942
12345