𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On hamiltonian claw-free graphs

✍ Scribed by E. Flandrin; J.L. Fouquet; H. Li

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
515 KB
Volume
111
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We show that every 3-connected claw-free graphs having at most 5S-10 vertices is hamiltonian, where 6 is the minimum degree. For regular 3-connected claw-free graphs, a related result was obtained by Li and Liu (preprint), but for nonregular claw-free graphs the best-known result comes from the work of Zhang ( 1988), with n <46 + 3.

bound can be strengthened to 56 -5 (see [4]). Our purpose is to show that the above regularity condition can be dropped. More precisely, we get the following theorem.

📜 SIMILAR VOLUMES

Hamiltonian N2-locally connected claw-fr
Hamiltonian N2-locally connected claw-free graphs
✍ Hong-Jian Lai; Yehong Shao; Mingquan Zhan 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

A graph G is N 2 -locally connected if for every vertex v in G, the edges not incident with v but having at least one end adjacent to v in G induce a connected graph. In 1990, Ryja ´c ˇek conjectured that every 3-connected N 2 -locally connected claw-free graph is Hamiltonian. This conjecture is pro

Claw-free 3-connected P11-free graphs ar
Claw-free 3-connected P11-free graphs are hamiltonian
✍ Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

## Abstract We show that every 3‐connected claw‐free graph which contains no induced copy of __P__~11~ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of __P__~12~ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph T

Hamiltonian cycles in 3-connected claw-f
Hamiltonian cycles in 3-connected claw-free graphs
✍ MingChu Li 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 437 KB 👁 2 views

## Abstract In this paper, we show that every 3‐connected claw‐free graph on n vertices with δ ≥ (__n__ + 5)/5 is hamiltonian. © 1993 John Wiley & Sons, Inc.

Hamiltonian cycles in 2-connected claw-f
Hamiltonian cycles in 2-connected claw-free-graphs
✍ Hao Li 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB 👁 2 views

## Abstract M. Matthews and D. Sumner have proved that of __G__ is a 2‐connected claw‐free graph of order __n__ such that δ ≧ (__n__ − 2)/3, then __G__ is hamiltonian. We prove that the bound for the minimum degree δ can be reduced to __n__/4 under the additional condition that __G__ is not in __F_

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 👁 3 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