Packing cycles in complete graphs

被引：21

作者：

Bryant, Darryn ^{[1
]}

Horsley, Daniel ^{[1
]}

机构：

[1] Univ Queensland, Dept Math, Brisbane, Qld 4072, Australia

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2008年 / 98卷 / 05期

基金：

澳大利亚研究理事会;

关键词：

cycle decompositions; graph decompositions; graph packing;

D O I：

10.1016/j.jctb.2007.12.004

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：1014 / 1037

页数：24

共 21 条

[1] On Alspach's conjecture with two even cycle lengths
Adams, P
Bryant, DE
Khodkar, A
[J]. DISCRETE MATHEMATICS, 2000, 223 (1-3) : 1 - 12
[2] Cycle decompositions of Kn and Kn-I
Alspach, B
Gavlas, H
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 81 (01) : 77 - 99
[3] Alspach B, 1981, DISCRETE MATH, V36, P333, DOI DOI 10.1016/S0012-365X(81)80029-5
[4] ANDERSEN LD, 1980, P LOND MATH SOC, V41, P557
[5] Packing circuits into KN
Balister, P
[J]. COMBINATORICS PROBABILITY & COMPUTING, 2001, 10 (06) : 463 - 499
[6] On the Alspach conjecture
Balister, PN
[J]. COMBINATORICS PROBABILITY & COMPUTING, 2001, 10 (02) : 95 - 125
[7] Decompositions into 2-regular subgraphs and equitable partial cycle decompositions
Bryant, D
Horsley, D
Maenhaut, B
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 93 (01) : 67 - 72
[8] Decompositions of complete graphs into triangles and Hamilton cycles
Bryant, D
Maenhaut, B
[J]. JOURNAL OF COMBINATORIAL DESIGNS, 2004, 12 (03) : 221 - 232
[9] BRYANT D, PROOF LINDNERS CONJE
[10] Bryant D., 2007, LONDON MATH SOC LECT, V346, P67

← 1 2 3 →