𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Every 3-connected claw-free Z8-free graph is Hamiltonian

✍ Scribed by Hong-Jian Lai; Liming Xiong; Huiya Yan; Jin Yan

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
115 KB
Volume
64
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this article, we first show that every 3‐edge‐connected graph with circumference at most 8 is supereulerian, which is then applied to show that a 3‐connected claw‐free graph without Z~8~ as an induced subgraph is Hamiltonian, where Z~8~ denotes the graph derived from identifying one end vertex of P~9~ (a path with 9 vertices) with one vertex of a triangle. The above two results are both best possible in a sense that the number 8 cannot be replaced by 9 and they also extend former results by Brousek et al. in (Discrete Math 196 (1999), 29–50) and by Łuczak and Pfender in (J Graph Theory 47 (2004), 111–121). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 1–11, 2010

📜 SIMILAR VOLUMES

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.

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

Every connected, locally connected nontr
Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
✍ David J. Oberly; Slobodan K. Simić; David P. Sumner 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB

## Abstract A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on __p__ ≥ 3 vertices and having no induced __K__~1,3~ is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtain

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_

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