Packing cycles in complete graphs

Darryn Bryant; Daniel Horsley

doi:10.1016/j.jctb.2007.12.004

Packing cycles in complete graphs

Darryn Bryant, Daniel Horsley

Research output: Contribution to journal › Article › Research › peer-review

21 Citations (Scopus)

Abstract

We introduce a new technique for packing pairwise edge-disjoint cycles of specified lengths in complete graphs and use it to prove several results. Firstly, we prove the existence of dense packings of the complete graph with pairwise edge-disjoint cycles of arbitrary specified lengths. We then use this result to prove the existence of decompositions of the complete graph of odd order into pairwise edge-disjoint cycles for a large family of lists of specified cycle lengths. Finally, we construct new maximum packings of the complete graph with pairwise edge-disjoint cycles of uniform length.

Original language	English
Pages (from-to)	1014 - 1037
Number of pages	24
Journal	Journal of Combinatorial Theory, Series B
Volume	98
Issue number	5
DOIs	https://doi.org/10.1016/j.jctb.2007.12.004
Publication status	Published - 2008
Externally published	Yes

Access to Document

10.1016/j.jctb.2007.12.004

Cite this

@article{b4fe41cd4fb94ffdb8356d708734f186,

title = "Packing cycles in complete graphs",

abstract = "We introduce a new technique for packing pairwise edge-disjoint cycles of specified lengths in complete graphs and use it to prove several results. Firstly, we prove the existence of dense packings of the complete graph with pairwise edge-disjoint cycles of arbitrary specified lengths. We then use this result to prove the existence of decompositions of the complete graph of odd order into pairwise edge-disjoint cycles for a large family of lists of specified cycle lengths. Finally, we construct new maximum packings of the complete graph with pairwise edge-disjoint cycles of uniform length.",

author = "Darryn Bryant and Daniel Horsley",

year = "2008",

doi = "10.1016/j.jctb.2007.12.004",

language = "English",

volume = "98",

pages = "1014 -- 1037",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press",

number = "5",

}

TY - JOUR

T1 - Packing cycles in complete graphs

AU - Bryant, Darryn

AU - Horsley, Daniel

PY - 2008

Y1 - 2008

N2 - We introduce a new technique for packing pairwise edge-disjoint cycles of specified lengths in complete graphs and use it to prove several results. Firstly, we prove the existence of dense packings of the complete graph with pairwise edge-disjoint cycles of arbitrary specified lengths. We then use this result to prove the existence of decompositions of the complete graph of odd order into pairwise edge-disjoint cycles for a large family of lists of specified cycle lengths. Finally, we construct new maximum packings of the complete graph with pairwise edge-disjoint cycles of uniform length.

AB - We introduce a new technique for packing pairwise edge-disjoint cycles of specified lengths in complete graphs and use it to prove several results. Firstly, we prove the existence of dense packings of the complete graph with pairwise edge-disjoint cycles of arbitrary specified lengths. We then use this result to prove the existence of decompositions of the complete graph of odd order into pairwise edge-disjoint cycles for a large family of lists of specified cycle lengths. Finally, we construct new maximum packings of the complete graph with pairwise edge-disjoint cycles of uniform length.

UR - http://www.sciencedirect.com/science/article/pii/S0095895608000026

U2 - 10.1016/j.jctb.2007.12.004

DO - 10.1016/j.jctb.2007.12.004

M3 - Article

SN - 0095-8956

VL - 98

SP - 1014

EP - 1037

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 5

ER -

Packing cycles in complete graphs

Abstract

Access to Document

Other files and links

Cite this