✦ LIBER ✦

Cycles through particular subgraphs of claw-free graphs

✍ Scribed by H. J. Broersma; M. Lu

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 301 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200409

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a 2‐connected claw‐free graph on n vertices, and let H be a subgraph of G. We prove that G has a cycle containing all vertices of H whenever α~3~(H) ≧ κ(G), where α~3~(H) denotes the maximum number of vertices of H that are pairwise at distance at least three in G, and κ(G) denotes the connectivity of G. This result is an analog of a result from the thesis of Fournier, and generalizes the result of Zhang that G is hamiltonian if the degree sum of any κ(G) + 1 pairwise nonadjacent vertices is at least n − κ(G). © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Hamilton cycles in claw-free graphs

✍ Cun-Quan Zhang 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB 👁 2 views

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

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_

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

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

Long cycles in subgraphs of (pseudo)rand

Long cycles in subgraphs of (pseudo)random directed graphs

✍ Ido Ben-Eliezer; Michael Krivelevich; Benny Sudakov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant __c__ = __c__(γ) such that the following holds. Let __G__ = (__V, E__) be a (pseudo)random directed graph on __n__ vertice