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 条
  • [1] On Hamiltonicity of regular graphs with bounded second neighborhoods
    Asratian, Armen S.
    Granholm, Jonas B.
    DISCRETE APPLIED MATHEMATICS, 2022, 316 : 75 - 86
  • [2] Hamiltonicity of 4-connected graphs
    Li, Hao
    Tian, Feng
    Xu, Zhi Xia
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2010, 26 (04) : 699 - 710
  • [3] Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity
    Qin, Yong
    Xiao, Wenjun
    Miklavic, Stefko
    DISCRETE MATHEMATICS, 2009, 309 (17) : 5426 - 5431
  • [4] Hamiltonicity of graphs perturbed by a random regular graph
    Diaz, Alberto Espuny
    Girao, Antonio
    RANDOM STRUCTURES & ALGORITHMS, 2023, 62 (04) : 857 - 886
  • [5] Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
    Wang, Rui
    Lau, Francis C. M.
    Zhao, Yingchao
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) : 2312 - 2320
  • [6] On Hamiltonicity of 3-Connected Claw-Free Graphs
    Tian, Runli
    Xiong, Liming
    Niu, Zhaohong
    GRAPHS AND COMBINATORICS, 2014, 30 (05) : 1261 - 1269
  • [7] ON IMPLICIT HEAVY SUBGRAPHS AND HAMILTONICITY OF 2-CONNECTED GRAPHS
    Zheng, Wei
    Widel, Wojciech
    Wang, Ligong
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (01) : 167 - 181
  • [8] On Hamiltonicity of 3-Connected Claw-Free Graphs
    Runli Tian
    Liming Xiong
    Zhaohong Niu
    Graphs and Combinatorics, 2014, 30 : 1261 - 1269
  • [9] PAIRS OF HEAVY SUBGRAPHS FOR HAMILTONICITY OF 2-CONNECTED GRAPHS
    Li, Binlong
    Ryjacek, Zdenek
    Wang, Ying
    Zhang, Shenggui
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) : 1088 - 1103
  • [10] Two Forbidden Subgraph Pairs for Hamiltonicity of 3-Connected Graphs
    Zhiquan Hu
    Houyuan Lin
    Graphs and Combinatorics, 2013, 29 : 1755 - 1775
12345