On Hamiltonicity of 3-Connected Claw-Free Graphs

Runli Tian; Liming Xiong; Zhaohong Niu

doi:10.1007/s00373-013-1343-7

On Hamiltonicity of 3-Connected Claw-Free Graphs

Runli Tian, Liming Xiong^*, Zhaohong Niu

^*Corresponding author for this work

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Lai, Shao and Zhan (J Graph Theory 48:142-146, 2005) showed that every 3-connected N₂-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.

Original language	English
Pages (from-to)	1261-1269
Number of pages	9
Journal	Graphs and Combinatorics
Volume	30
Issue number	5
DOIs	https://doi.org/10.1007/s00373-013-1343-7
Publication status	Published - Sept 2014

Keywords

Claw-free graph
Hamiltonicity
Locally disconnected vertex
Singular edge
Singular k-cycle (property)

Access to Document

10.1007/s00373-013-1343-7

Cite this

Tian, R., Xiong, L., & Niu, Z. (2014). On Hamiltonicity of 3-Connected Claw-Free Graphs. Graphs and Combinatorics, 30(5), 1261-1269. https://doi.org/10.1007/s00373-013-1343-7

@article{063444daec7a4feda062a0e768cdccc4,

title = "On Hamiltonicity of 3-Connected Claw-Free Graphs",

abstract = "Lai, Shao and Zhan (J Graph Theory 48:142-146, 2005) showed that every 3-connected N2-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.",

keywords = "Claw-free graph, Hamiltonicity, Locally disconnected vertex, Singular edge, Singular k-cycle (property)",

author = "Runli Tian and Liming Xiong and Zhaohong Niu",

year = "2014",

month = sep,

doi = "10.1007/s00373-013-1343-7",

language = "English",

volume = "30",

pages = "1261--1269",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "5",

}

TY - JOUR

T1 - On Hamiltonicity of 3-Connected Claw-Free Graphs

AU - Tian, Runli

AU - Xiong, Liming

AU - Niu, Zhaohong

PY - 2014/9

Y1 - 2014/9

N2 - Lai, Shao and Zhan (J Graph Theory 48:142-146, 2005) showed that every 3-connected N2-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.

AB - Lai, Shao and Zhan (J Graph Theory 48:142-146, 2005) showed that every 3-connected N2-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.

KW - Claw-free graph

KW - Hamiltonicity

KW - Locally disconnected vertex

KW - Singular edge

KW - Singular k-cycle (property)

UR - http://www.scopus.com/inward/record.url?scp=84906350561&partnerID=8YFLogxK

U2 - 10.1007/s00373-013-1343-7

DO - 10.1007/s00373-013-1343-7

M3 - Article

AN - SCOPUS:84906350561

SN - 0911-0119

VL - 30

SP - 1261

EP - 1269

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 5

ER -

On Hamiltonicity of 3-Connected Claw-Free Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this