✦ LIBER ✦

Small cycles in Hamiltonian graphs

✍ Scribed by Uwe Schelten; Ingo Schiermeyer

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 733 KB
Volume: 79
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)00043-7

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that if a graph G on n > 32 vertices is hamiltonian and has two nonadjacent vertices u and u with d(u) + d(u) 3 n + z where z = 0 if n is odd and z = 1 if n is even, then G contains all cycles of length m where 3 < m < 1/5(n + 13).

📜 SIMILAR VOLUMES

Hamiltonian cycles in n-extendable graph

Hamiltonian cycles in n-extendable graphs

✍ Ken-ichi Kawarabayashi; Katsuhiro Ota; Akira Saito 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB

## 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

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

Hamiltonian cycles in random regular gra

Hamiltonian cycles in random regular graphs

✍ T.I Fenner; A.M Frieze 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 484 KB

Polyhedral graphs without hamiltonian cy

Polyhedral graphs without hamiltonian cycles

✍ Hansjoachim Walther 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 309 KB

There is a constructed sequence of polyhedral cyclically 5-connected cubic non-hamiltonian graphs having only 5-gons and 8-gons as faces.

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

Disjoint Hamiltonian cycles in recursive

Disjoint Hamiltonian cycles in recursive circulant graphs

✍ C. Micheneau 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 499 KB

We show in this paper that the circulant graph G( 2"', 4) is Hamiltonian decomposable, and propose a recursive construction method. This is a partial answer to a problem posed by B. Alspach. @