✦ LIBER ✦

Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor

✍ Scribed by Richard A. Brualdi; Michael W. Schroeder

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 190 KB
Volume: 19
Category: Article
ISSN: 1063-8539
DOI: 10.1002/jcd.20257

No coin nor oath required. For personal study only.

✦ Synopsis

Let n ≥ 2 be an integer. The complete graph K n with a 1-factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K n -F has a decomposition into Hamilton cycles which are symmetric with respect to the 1-factor F if and only if n ≡ 2,4 mod 8. We also show that the complete bipartite graph K n,n has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1-factor of K n,n , then K n,n -F has a symmetric Hamilton cycle decomposition if and only if n is odd. q 2010 Wiley

📜 SIMILAR VOLUMES

Symmetric Hamilton cycle decompositions

Symmetric Hamilton cycle decompositions of the complete graph

✍ Jin Akiyama; Midori Kobayashi; Gisaku Nakamura 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 1 views

Decompositions of complete graphs into t

Decompositions of complete graphs into triangles and Hamilton cycles

✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 1 views

## Abstract For all odd integers __n__ ≥ 1, let __G~n~__ denote the complete graph of order __n__, and for all even integers __n__ ≥ 2 let __G~n~__ denote the complete graph of order __n__ with the edges of a 1‐factor removed. It is shown that for all non‐negative integers __h__ and __t__ and all p

Hamilton cycle rich two-factorizations o

Hamilton cycle rich two-factorizations of complete graphs

✍ Darryn Bryant 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract For all integers __n__ ≥ 5, it is shown that the graph obtained from the __n__‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order __n__. This result is used to prove s

Hamilton decompositions of complete mult

Hamilton decompositions of complete multipartite graphs with any 2-factor leave

✍ C. D. Leach; C. A. Rodger 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB 👁 1 views

## Abstract For __m__ ≥ 1 and __p__ ≥ 2, given a set of integers __s__~1~,…,__s__~__q__~ with $s\_j \geq p+1$ for $1 \leq j \leq q$ and ${\sum \_{j\,=\,1}^q} s\_j = mp$, necessary and sufficient conditions are found for the existence of a hamilton decomposition of the complete __p__‐partite graph $

Decomposition of the complete graph plus

Decomposition of the complete graph plus a 1-factor into cycles of equal length

✍ Mateja Šajna 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 354 KB 👁 1 views

## Abstract We determine the necessary and sufficient conditions for the existence of a decomposition of the complete graph of even order with a 1‐factor added into cycles of equal length. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 170–207, 2003; Published online in Wiley InterScience (www

A 1-factorization of the line graphs of

A 1-factorization of the line graphs of complete graphs

✍ Brian Alspach 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB 👁 1 views

## Abstract A 1‐factorization is constructed for the line graph of the complete graph __K~n~__ when __n__ is congruent to 0 or 1 modulo 4.