On Hamiltonicity of 3-Connected Claw-Free Graphs

被引：1
|
作者：
Tian, Runli [1 ]
Xiong, Liming [1 ,2 ]
Niu, Zhaohong [3 ]
机构：
[1] Beijing Inst Technol, Sch Math, Beijing 100081, Peoples R China
[2] Qinghai Univ Nationalities, Dept Math, Xining 810000, Peoples R China
[3] Shanxi Univ, Sch Math Sci, Taiyuan 030006, Peoples R China
来源：
GRAPHS AND COMBINATORICS | 2014年 / 30卷 / 05期
基金：
北京市自然科学基金;
关键词：
Claw-free graph; Hamiltonicity; Locally disconnected vertex; Singular edge; Singular k-cycle (property);
D O I：
10.1007/s00373-013-1343-7
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Lai, Shao and Zhan (J Graph Theory 48:142-146, 2005) showed that every 3-connected N (2)-locally connected claw-free graph is Hamiltonian. In this paper, we generalize this result and show that every 3-connected claw-free graph G such that every locally disconnected vertex lies on some induced cycle of length at least 4 with at most 4 edges contained in some triangle of G is Hamiltonian. It is best possible in some sense.
引用
收藏
页码：1261 / 1269
页数：9
相关论文
共 50 条
  • [41] Non-traceability of large connected claw-free graphs
    Frydrych, W
    Skupien, Z
    JOURNAL OF GRAPH THEORY, 1998, 27 (02) : 75 - 86
  • [42] Hamiltonian properties of almost locally connected claw-free graphs
    Chen, Xiaodong
    Li, MingChu
    Liao, Wei
    Broersma, Hajo
    ARS COMBINATORIA, 2016, 124 : 95 - 109
  • [43] Induced Subgraphs with Large Degrees at End-vertices for Hamiltonicity of Claw-free Graphs
    Roman ADA
    Bin Long LI
    Bo NING
    Sheng Gui ZHANG
    Acta Mathematica Sinica,English Series, 2016, (07) : 845 - 855
  • [44] The *-closure for graphs and claw-free graphs
    Cada, Roman
    DISCRETE MATHEMATICS, 2008, 308 (23) : 5585 - 5596
  • [45] -Connectivity of Claw-Free Graphs
    Huang, Ziwen
    Li, Xiangwen
    Ma, Jianqing
    GRAPHS AND COMBINATORICS, 2017, 33 (01) : 123 - 140
  • [46] Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs
    Roman Čada
    Bin Long Li
    Bo Ning
    Sheng Gui Zhang
    Acta Mathematica Sinica, English Series, 2016, 32 : 845 - 855
  • [47] Hamiltonian claw-free graphs with locally disconnected vertices
    Tian, Runli
    Xiong, Liming
    DISCRETE MATHEMATICS, 2015, 338 (11) : 2042 - 2050
  • [48] Induced Subgraphs with Large Degrees at End-vertices for Hamiltonicity of Claw-free Graphs
    Cada, Roman
    Li, Bin Long
    Ning, Bo
    Zhang, Sheng Gui
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2016, 32 (07) : 845 - 855
  • [49] 2-Factors in claw-free graphs with locally disconnected vertices
    An, Mingqiang
    Xiong, Liming
    Tian, Runli
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2015, 65 (02) : 317 - 330
  • [50] Spanning 3-ended trees in k-connected claw-free graphs
    Chen, Xiaodong
    Li, MingChu
    Xu, Meijin
    ARS COMBINATORIA, 2017, 131 : 161 - 168
12345