On hamiltonicity of 2-connected claw-free graphs

Run li Tian*, Li ming Xiong

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
Plum Print visual indicator of research metrics
  • Citations
    • Citation Indexes: 1
  • Captures
    • Readers: 3
see details

Abstract

A graph G has the hourglass property if every induced hourglass S (a tree with a degree sequence 22224) contains two non-adjacent vertices which have a common neighbor in G - V (S). For an integer k ≥ 4, a graph G has the single k-cycle property if every edge of G, which does not lie in a triangle, lies in a cycle C of order at most k such that C has at least edges which do not lie in a triangle, and they are not adjacent. In this paper, we show that every hourglass-free claw-free graph G of δ(G) ≥ 3 with the single 7-cycle property is Hamiltonian and is best possible; we also show that every claw-free graph G of δ(G) ≥ 3 with the hourglass property and with single 6-cycle property is Hamiltonian.

Original languageEnglish
Pages (from-to)234-242
Number of pages9
JournalApplied Mathematics
Volume27
Issue number2
DOIs
Publication statusPublished - Jun 2012

Keywords

  • Hamiltonian
  • claw-free graph
  • closure
  • the hourglass property
  • the single k-cycle property

Fingerprint

Dive into the research topics of 'On hamiltonicity of 2-connected claw-free graphs'. Together they form a unique fingerprint.

Cite this

Tian, R. L., & Xiong, L. M. (2012). On hamiltonicity of 2-connected claw-free graphs. Applied Mathematics, 27(2), 234-242. https://doi.org/10.1007/s11766-012-2835-6