𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximal K3's and Hamiltonicity of 4-connected claw-free graphs

✍ Scribed by Jun Fujisawa; Katsuhiro Ota

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
255 KB
Volume
70
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let cl(G) denote Ryjáček's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N~G~(T)] is cyclically 3‐connected if T is a maximal K~3~ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Hamilton connectivity of line graphs and
Hamilton connectivity of line graphs and claw-free graphs
✍ Zhiquan Hu; Feng Tian; Bing Wei 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Let __G__ be a graph and let __V__~0~ = {ν∈ __V__(__G__): __d__~__G__~(ν) = 6}. We show in this paper that: (i) if __G__ is a 6‐connected line graph and if |__V__~0~| ≤ 29 or __G__[__V__~0~] contains at most 5 vertex disjoint __K__~4~'s, then __G__ is Hamilton‐connected; (ii) every 8‐co

Hourglasses and Hamilton cycles in 4-con
Hourglasses and Hamilton cycles in 4-connected claw-free graphs
✍ Tomáš Kaiser; MingChu Li; Zdeněk Ryjáček; Liming Xiong 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 1 views

## Abstract We show that if __G__ is a 4‐connected claw‐free graph in which every induced hourglass subgraph __S__ contains two non‐adjacent vertices with a common neighbor outside __S__, then __G__ is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamilton

On factors of 4-connected claw-free grap
On factors of 4-connected claw-free graphs
✍ H. J. Broersma; M. Kriesell; Z. Ryjác̆ek 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian,

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

Critical graphs for subpancyclicity of 3
Critical graphs for subpancyclicity of 3-connected claw-free graphs
✍ Ronald J. Gould; Tomasz Łuczak; Florian Pfender 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

## Abstract Let ${\cal{F}}\_{k}$ be the family of graphs __G__ such that all sufficiently large __k__ ‐connected claw‐free graphs which contain no induced copies of __G__ are subpancyclic. We show that for every __k__≥3 the family ${\cal{F}}\_{1}k$ is infinite and make the first step toward the c