✦ LIBER ✦

Fair Hamilton Decompositions of Complete Multipartite Graphs

✍ Scribed by C.D. Leach; C.A. Rodger

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 88 KB
Volume: 85
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2104

No coin nor oath required. For personal study only.

✦ Synopsis

A fair hamilton decomposition of the complete multipartite graph G is a set of hamilton cycles in G whose edges partition the edges of G in such a way that, for each pair of parts and for each pair of hamilton cycles H 1 and H 2 , the difference in the number of edges in H 1 and H 2 joining vertices in these two parts is at most one. In this paper we completely settle the existence of such decompositions. The proof is constructive, using the method of amalgamations (graph homomorphisms).

📜 SIMILAR VOLUMES

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 $

Maximal sets of hamilton cycles in compl

Maximal sets of hamilton cycles in complete multipartite graphs

✍ Mike Daven; J. A. MacDougall; C. A. Rodger 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 2 views

## Abstract A set __S__ of edge‐disjoint hamilton cycles in a graph __G__ is said to be __maximal__ if the edges in the hamilton cycles in __S__ induce a subgraph __H__ of __G__ such that __G__ − __E__(__H__) contains no hamilton cycles. In this context, the spectrum __S__(__G__) of a graph __G__ i

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

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

Hamilton decompositions of some line gra

Hamilton decompositions of some line graphs

✍ David A. Pike 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 361 KB

## Abstract The main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if __G__ is a bipartite (2__k__ + 1)‐regular graph that is Hamilton decomposable, then the line graph, __L__(__G__), of __G__ is also Hamilton decomposable. A similar

Symmetric Hamilton cycle decompositions

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

✍ Richard A. Brualdi; Michael W. Schroeder 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 1 views

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