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

^*此作品的通讯作者

数学学院

University of West Bohemia
Dalian University of Technology
Tianjin University
Jiangxi Normal University

科研成果: 期刊稿件 › 文章 › 同行评审

8 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	267-276
页数	10
期刊	Journal of Graph Theory
卷	48
期	4
DOI	https://doi.org/10.1002/jgt.20056
出版状态	已出版 - 4月 2005

访问文件

10.1002/jgt.20056

其它文件与链接

链接到 Scopus 的出版物

引用此

@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 - https://www.scopus.com/pages/publications/17644400666

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

摘要

访问文件

其它文件与链接

学术指纹

引用此