✦ LIBER ✦

Decompositions of complete graphs into triangles and Hamilton cycles

✍ Scribed by Darryn Bryant; Barbara Maenhaut

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 121 KB
Volume: 12
Category: Article
ISSN: 1063-8539
DOI: 10.1002/jcd.10063

No coin nor oath required. For personal study only.

✦ Synopsis

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 positive integers n, G~n~ can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3__t__ is the number of edges in G~n~. © 2004 Wiley Periodicals, Inc.

📜 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

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

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

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

Random Matchings Which Induce Hamilton C

Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs

✍ Jeong Han Kim; Nicholas C. Wormald 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 215 KB

Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set