Cycle decompositions V: Complete graphs into cycles of arbitrary lengths

By Darryn E. Bryant, Daniel Horsley, William Pettersson. 2012

57 citations recorded by the source corpus.

We show that the complete graph on n vertices can be decomposed into t cycles of specified lengths m1, …, mt if and only if n is odd, 3⩽mi⩽n for i=1, …, t, and m1+⋯+mt=(n2) . We also show that the complete graph on n vertices can be decomposed into a perfect matching and t cycles of specified lengths m1, …, mt if and only if n is even, 3⩽mi⩽n for i=1, …, t, and m1+⋯+mt=(n2)−n/2 .

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/6313546818c475c6af5187c1ce1eef6842c84e09

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Deryk Osthus
2. D. Kühn
3. Peter Keevash
4. Richard Mycroft

In Electrical and Electronic Engineering

1. Deryk Osthus
2. D. Kühn
3. Peter Keevash
4. Richard Mycroft

Citations in the corpus

• Hamilton cycles in graphs and hypergraphs: an extremal perspective (2014, result): “Digraphs are discussed in [102], though some very recent results on digraphs are also included here.”