✦ LIBER ✦

Hamiltonian cycles in n-extendable graphs

✍ Scribed by Ken-ichi Kawarabayashi; Katsuhiro Ota; Akira Saito

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 88 KB
Volume: 40
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph G of order at least 2__n__+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy deg~G~ x+deg~G~ y ≥ p − n − 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002

📜 SIMILAR VOLUMES

Hamiltonian cycles in cayley color graph

Hamiltonian cycles in cayley color graphs

✍ Joseph B. Klerlein 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 1 views

## Abstract A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph __D__~Δ~(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are

On certain Hamiltonian cycles in planar

On certain Hamiltonian cycles in planar graphs

✍ B�hme, T.; Harant, J.; Tk�?, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that mus

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_

Disjoint Hamiltonian cycles in fan 2k-ty

Disjoint Hamiltonian cycles in fan 2k-type graphs

✍ Zhou Sanming 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB

## Abstract It is conjectured that a 2(__k__ + 1)‐connected graph of order __p__ contains __k__ + 1 pairwise disjoint Hamiltonian cycles if no two of its vertices that have degree less than 1/2 + 2__k__ are distance two apart. This is proved in detail for __k__ = 1. Similar arguments establish the

A note on n-extendable graphs

✍ Qinglin Yu 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract A graph __G__ having a perfect matching is called n‐__extendable__ if every matching of size __n__ of __G__ can be extended to a perfect matching. In this note, we show that if __G__ is an __n__‐extendable nonbipartite graph, then __G__ + __e__ is (__n__ ‐ 1)‐extendable for any edge e ϵ