Hourglasses and Hamilton cycles in 4-connected claw-free graphs

Tomáš Kaiser; Ming Chu Li; Zdeněk Ryjáček; Liming Xiong

doi:10.1002/jgt.20056

Hourglasses and Hamilton cycles in 4-connected claw-free graphs

Tomáš Kaiser^*, Ming Chu Li, Zdeněk Ryjáček, Liming Xiong

^*Corresponding author for this work

School of Mathematics and Statistics

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

8 Citations (Scopus)

Abstract

We show that if G is a 4-connected claw-free graph in which every induced hourglass subgraph S contains two non-adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4-connected claw-free, hourglass-free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner.

Original language	English
Pages (from-to)	267-276
Number of pages	10
Journal	Journal of Graph Theory
Volume	48
Issue number	4
DOIs	https://doi.org/10.1002/jgt.20056
Publication status	Published - Apr 2005

Keywords

Claw-free graph
Closure
Hamilton cycle
Hourglass

Access to Document

10.1002/jgt.20056

Cite this

@article{894e8b839e6548dbabd1084b2066b039,

title = "Hourglasses and Hamilton cycles in 4-connected claw-free graphs",

abstract = "We show that if G is a 4-connected claw-free graph in which every induced hourglass subgraph S contains two non-adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4-connected claw-free, hourglass-free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner.",

keywords = "Claw-free graph, Closure, Hamilton cycle, Hourglass",

author = "Tom{\'a}{\v s} Kaiser and Li, {Ming Chu} and Zden{\v e}k Ryj{\'a}{\v c}ek and Liming Xiong",

year = "2005",

month = apr,

doi = "10.1002/jgt.20056",

language = "English",

volume = "48",

pages = "267--276",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Hourglasses and Hamilton cycles in 4-connected claw-free graphs

AU - Kaiser, Tomáš

AU - Li, Ming Chu

AU - Ryjáček, Zdeněk

AU - Xiong, Liming

PY - 2005/4

Y1 - 2005/4

N2 - We show that if G is a 4-connected claw-free graph in which every induced hourglass subgraph S contains two non-adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4-connected claw-free, hourglass-free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner.

AB - We show that if G is a 4-connected claw-free graph in which every induced hourglass subgraph S contains two non-adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4-connected claw-free, hourglass-free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner.

KW - Claw-free graph

KW - Closure

KW - Hamilton cycle

KW - Hourglass

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

U2 - 10.1002/jgt.20056

DO - 10.1002/jgt.20056

M3 - Article

AN - SCOPUS:17644400666

SN - 0364-9024

VL - 48

SP - 267

EP - 276

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Hourglasses and Hamilton cycles in 4-connected claw-free graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this