On the Independence Number of Traceable 2-Connected Claw-Free Graphs

Shipeng Wang; Liming Xiong

doi:10.7151/dmgt.2113

On the Independence Number of Traceable 2-Connected Claw-Free Graphs

Shipeng Wang
, Liming Xiong

数学学院

Beijing Institute of Technology

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

摘要

A well-known theorem by Chvátal-Erdoos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111-135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.

源语言	英语
页（从-至）	925-937
页数	13
期刊	Discussiones Mathematicae - Graph Theory
卷	39
期	4
DOI	https://doi.org/10.7151/dmgt.2113
出版状态	已出版 - 1 11月 2019

访问文件

10.7151/dmgt.2113

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{023ab47c640b40588f024c3556ec3b9b,

title = "On the Independence Number of Traceable 2-Connected Claw-Free Graphs",

abstract = "A well-known theorem by Chv{\'a}tal-Erdoos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111-135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.",

keywords = "closure, independence number, matching number, traceability, trail",

author = "Shipeng Wang and Liming Xiong",

note = "Publisher Copyright: {\textcopyright} 2019 Shipeng Wang et al., published by Sciendo.",

year = "2019",

month = nov,

day = "1",

doi = "10.7151/dmgt.2113",

language = "English",

volume = "39",

pages = "925--937",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "4",

}

TY - JOUR

T1 - On the Independence Number of Traceable 2-Connected Claw-Free Graphs

AU - Wang, Shipeng

AU - Xiong, Liming

PY - 2019/11/1

Y1 - 2019/11/1

N2 - A well-known theorem by Chvátal-Erdoos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111-135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.

AB - A well-known theorem by Chvátal-Erdoos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111-135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.

KW - closure

KW - independence number

KW - matching number

KW - traceability

KW - trail

UR - https://www.scopus.com/pages/publications/85068402124

U2 - 10.7151/dmgt.2113

DO - 10.7151/dmgt.2113

M3 - Article

AN - SCOPUS:85068402124

SN - 1234-3099

VL - 39

SP - 925

EP - 937

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 4

ER -

On the Independence Number of Traceable 2-Connected Claw-Free Graphs

摘要

访问文件

其它文件与链接

指纹

引用此