𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

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

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
85 KB
Volume
44
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 $K_{m,\ldots,m} - E(U)$, where U is a 2‐factor of $K_{m,\ldots,m}$ consisting of q cycles, the __j__th cycle having length s~j~. This result is then used to completely solve the problem when p = 3, removing the condition that $s_j\ge p+1$. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 208–214, 2003

📜 SIMILAR VOLUMES

Fair Hamilton Decompositions of Complete
Fair Hamilton Decompositions of Complete Multipartite Graphs
✍ C.D. Leach; C.A. Rodger 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 88 KB

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

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

Nondisconnecting disentanglements of ama
Nondisconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs
✍ C. D. Leach; C. A. Rodger 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## Abstract In this paper necessary and sufficient conditions are found for an edge‐colored graph __H__ to be the homomorphic image of a 2‐factorization of a complete multipartite graph __G__ in which each 2‐factor of __G__ has the same number of components as its corresponding color class in __H__