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 条
  • [21] A Generalization of Implicit Ore-condition for Hamiltonicity ofk-connected Graphs
    Cai, Jun-qing
    Wang, Lin
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2020, 36 (03): : 620 - 626
  • [22] Hamiltonicity in random graphs is born resilient
    Montgomery, Richard
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 139 : 316 - 341
  • [23] Minimum degree conditions for the Hamiltonicity of 3-connected claw-free graphs
    Chen, Zhi-Hong
    Lai, Hong-Jian
    Xiong, Liming
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 167 - 186
  • [24] A note on degree conditions for hamiltonicity in 2-connected claw-free graphs
    Kovárík, O
    Mulac, M
    Ryjácek, Z
    DISCRETE MATHEMATICS, 2002, 244 (1-3) : 253 - 268
  • [25] HAMILTONICITY IN PARTLY CLAW-FREE GRAPHS
    Abbas, Moncef
    Benmeziane, Zineb
    RAIRO-OPERATIONS RESEARCH, 2009, 43 (01) : 103 - 113
  • [26] On the Hamiltonicity of random bipartite graphs
    Yilun Shang
    Indian Journal of Pure and Applied Mathematics, 2015, 46 : 163 - 173
  • [27] Hamiltonicity of Token Graphs of Some Join Graphs
    Adame, Luis Enrique
    Rivera, Luis Manuel
    Trujillo-Negrete, Ana Laura
    SYMMETRY-BASEL, 2021, 13 (06):
  • [28] ROBUST HAMILTONICITY OF DIRAC GRAPHS
    Krivelevich, Michael
    Lee, Choongbum
    Sudakov, Benny
    TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2014, 366 (06) : 3095 - 3130
  • [29] Hamiltonicity of covering graphs of trees
    Bradshaw, Peter
    Ge, Zhilin
    Stacho, Ladislav
    DISCRETE APPLIED MATHEMATICS, 2024, 357 : 449 - 464
  • [30] The matching number and Hamiltonicity of graphs
    Li, Rao
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 1094 - 1095
12345