𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Toughness and hamiltonicity in almost claw-free graphs

✍ Scribed by Broersma, H.J.; Ryj�?ek, Z.; Schiermeyer, I.

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
491 KB
Volume
21
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Some known results on claw-free (Kl,3-free) graphs are generalized to the larger class of almost claw-free graphs which were introduced by RyjaEek. In particular, w e show that a 2-connected almost claw-free graph is I-tough, and that a 2-connected almost claw-free graph on n vertices is hamiltonian if 6 2 i ( n -2), thereby (partly) generalizing results of Matthews and Sumner. Finally, w e use a result of Bauer et al. to show that a 2-connected almost claw-free graph on n vertices is hamiltonian if

for all independent sets of vertices u, u , and w. 0 1996

📜 SIMILAR VOLUMES

Closure and stable Hamiltonian propertie
Closure and stable Hamiltonian properties in claw-free graphs
✍ Brandt, Stephan; Favaron, Odile; Ryj�?ek, Zden?k 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 171 KB 👁 2 views

In the class of k-connected claw-free graphs, we study the stability of some Hamiltonian properties under a closure operation introduced by the third author. We prove that (i) the properties of pancyclicity, vertex pancyclicity and cycle extendability are not stable for any k (i.e., for any of these

Independence and hamiltonicity in 3-domi
Independence and hamiltonicity in 3-domination-critical graphs
✍ Favaron, Odile; Tian, Feng; Zhang, Lei 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisf

Closure, 2-factors, and cycle coverings
Closure, 2-factors, and cycle coverings in claw-free graphs
✍ Ryj�?ek, Zden?k; Saito, Akira; Schelp, R. H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 2 views

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217-224). For a claw-free graph G and its closure cl(G), we prove: ( 1 (2) G

Non-traceability of large connected claw
Non-traceability of large connected claw-free graphs
✍ Frydrych, Wac?w; Skupie?, Zdzis?aw 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 2 views

Let G be a connected claw-free graph on n vertices. Let σ 3 (G) be the minimum degree sum among triples of independent vertices in G. It is proved that if σ 3 (G) ≥ n-3 then G is traceable or else G is one of graphs G n each of which comprises three disjoint nontrivial complete graphs joined togethe