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

School of Mathematics and Statistics

Beijing Institute of Technology

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

Abstract

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.

Original language	English
Pages (from-to)	925-937
Number of pages	13
Journal	Discussiones Mathematicae - Graph Theory
Volume	39
Issue number	4
DOIs	https://doi.org/10.7151/dmgt.2113
Publication status	Published - 1 Nov 2019

Keywords

closure
independence number
matching number
traceability
trail

Access to Document

10.7151/dmgt.2113

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this