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

Szczegóły
Opis

Tytuł:: On the Independence Number of Traceable 2-Connected Claw-Free Graphs
Autorzy:: Wang, Shipeng
Xiong, Liming
Data publikacji:: 2019-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: traceability
independence number
matching number
trail
closure
Język:: angielski
Prawa:: CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Źródło:: Discussiones Mathematicae Graph Theory; 2019, 39, 4; 925-937
2083-5892
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

A well-known theorem by Chvátal-Erdőos [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.

Informacja