✦ LIBER ✦

Cycle decompositions of complete multigraphs

✍ Scribed by Darryn Bryant; Daniel Horsley; Barbara Maenhaut; Benjamin R. Smith

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

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that the obvious necessary conditions for the existence of a decomposition of the complete multigraph with n vertices and with k edges joining each pair of distinct vertices into m-cycles, or into m-cycles and a perfect matching, are also sufficient. This result follows as an easy consequence of more general results which are obtained on decompositions of complete multigraphs into cycles of varying lengths.

📜 SIMILAR VOLUMES

Cycle decompositions of complete multigr

Cycle decompositions of complete multigraphs

✍ Benjamin R. Smith 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

## Abstract In this paper we establish necessary and sufficient conditions for decomposing the complete multigraph λ__K__~__n__~ into cycles of length λ, and the λ‐fold complete symmetric digraph λ__K__ into directed cycles of length λ. As a corollary to these results we obtain necessary and suffic

Decompositions of Complete Multigraphs R

Decompositions of Complete Multigraphs Related to Hadamard Matrices

✍ David A Gregory; Kevin N Vander Meulen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Let bp(+K v ) be the minimum number of complete bipartite subgraphs needed to partition the edge set of +K v , the complete multigraph with + edges between each pair of its v vertices. Many papers have examined bp(+K v ) for v 2+. For each + and v with v 2+, it is shown here that if certain Hadamard

Path decompositions of multigraphs

✍ Leizhen Cai 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 494 KB

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and p(x) respectively. Define the least even integer 2 p(x), if d(x) is even, the least odd integer 2 p(x), if d(x) is odd. In this paper it is shown that every multigraph G admits a faithful 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

Applying a proof of tverberg to complete

Applying a proof of tverberg to complete bipartite decompositions of digraphs and multigraphs

✍ Dan Pritikin 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

Graham and Pollak 121 proved that n -1 is the minimum number of edge-disjoint complete bipartite subgraphs into which the edges of K,, decompose. Tverberg 161, using a linear algebraic technique, was the first to give a simple proof of this result. We apply Tverberg's technique to obtain results for

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