Page 63 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 63
iusz Meszka: Combinatorial Designs 51
(2, 3, 7, 4), (2, 7, 6, 8), (3, 4, 8, 5)}.
Theorem 26. A k -cycle system of order n exists if and only if:
(1) n ≥ k ≥ 3,
(2) n is odd,
(3) 2k |n(n − 1).
A k -cycle system (X , ) of order n is resolvable if the k -cycles belonging to C can be
partitioned into parallel classes.
Example 20. A resolvable 5-cycle system (X , ) of order 15:
V = {0, 1, . . . , 14},
R1 = {(0, 1, 3, 6, 9), (2, 7, 8, 10, 13), (4, 11, 5, 14, 12)},
R1 = {(0, 2, 5, 8, 6), (1, 12, 9, 7, 13), (3, 10, 4, 14, 11)},
R1 = {(0, 3, 13, 4, 5), (1, 8, 2, 14, 9), (6, 10, 7, 12, 11)},
R2 = {(0, 4, 2, 1, 10), (3, 7, 11, 9, 8), (5, 12, 6, 14, 13)},
R1 = {(0, 7, 1, 14, 8), (2, 6, 4, 3, 12), (5, 10, 11, 13, 9)},
R1 = {(0, 11, 8, 13, 12), (1, 4, 7, 5, 6), (2, 9, 3, 14, 10)},
R3 = {(0, 13, 6, 7, 14), (1, 5, 3, 2, 11), (4, 8, 12, 10, 9)}.
Theorem 27. A resolvable k -cycle system of order n exists if and only if:
(1) n ≥ k ≥ 3,
(2) n is odd,
(3) k |n.
Theorem 28. Let n be odd, 3 ≤ m1, m2, . . . , mt ≤ n and m1 + m2 + . . . + mt = n (n − 1)/2.
Then there exists a decomposition of Kn into t cycles of lengths m1, m2, . . . , mt .
Oberwolfach Problem. Let n be odd, 3 ≤ m1, m2, . . . , mt ≤ n and m1 + m2 + . . . + mt =
n . Does the complete graph Kn have a 2-factorization in which every 2-factor consists of
cycles of lengths m1, m2, . . . , mt ?
The Oberwolfach problem has an affirmative solution for n ≤ 40 and every admissi-
ble collection of cycles lengths, with the exception of two cases:
(1) m1 = 4, m2 = 5
(2) m1 = m2 = 3, m3 = 5.
Exercise 22.
Construct a 5-cycle system of order 11.
Exercise 23.
Construct a resolvable 5-cycle system of order 25.
(2, 3, 7, 4), (2, 7, 6, 8), (3, 4, 8, 5)}.
Theorem 26. A k -cycle system of order n exists if and only if:
(1) n ≥ k ≥ 3,
(2) n is odd,
(3) 2k |n(n − 1).
A k -cycle system (X , ) of order n is resolvable if the k -cycles belonging to C can be
partitioned into parallel classes.
Example 20. A resolvable 5-cycle system (X , ) of order 15:
V = {0, 1, . . . , 14},
R1 = {(0, 1, 3, 6, 9), (2, 7, 8, 10, 13), (4, 11, 5, 14, 12)},
R1 = {(0, 2, 5, 8, 6), (1, 12, 9, 7, 13), (3, 10, 4, 14, 11)},
R1 = {(0, 3, 13, 4, 5), (1, 8, 2, 14, 9), (6, 10, 7, 12, 11)},
R2 = {(0, 4, 2, 1, 10), (3, 7, 11, 9, 8), (5, 12, 6, 14, 13)},
R1 = {(0, 7, 1, 14, 8), (2, 6, 4, 3, 12), (5, 10, 11, 13, 9)},
R1 = {(0, 11, 8, 13, 12), (1, 4, 7, 5, 6), (2, 9, 3, 14, 10)},
R3 = {(0, 13, 6, 7, 14), (1, 5, 3, 2, 11), (4, 8, 12, 10, 9)}.
Theorem 27. A resolvable k -cycle system of order n exists if and only if:
(1) n ≥ k ≥ 3,
(2) n is odd,
(3) k |n.
Theorem 28. Let n be odd, 3 ≤ m1, m2, . . . , mt ≤ n and m1 + m2 + . . . + mt = n (n − 1)/2.
Then there exists a decomposition of Kn into t cycles of lengths m1, m2, . . . , mt .
Oberwolfach Problem. Let n be odd, 3 ≤ m1, m2, . . . , mt ≤ n and m1 + m2 + . . . + mt =
n . Does the complete graph Kn have a 2-factorization in which every 2-factor consists of
cycles of lengths m1, m2, . . . , mt ?
The Oberwolfach problem has an affirmative solution for n ≤ 40 and every admissi-
ble collection of cycles lengths, with the exception of two cases:
(1) m1 = 4, m2 = 5
(2) m1 = m2 = 3, m3 = 5.
Exercise 22.
Construct a 5-cycle system of order 11.
Exercise 23.
Construct a resolvable 5-cycle system of order 25.
