CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013

Cycle Decompositions of Graphs I
Chair: Mateja Sajna (University of Ottawa)
Org: Andrea Burgess (Ryerson University) and Mateja Sajna (University of Ottawa)
[PDF]

DARRYN BRYANT, University of Queensland
Repacking in cycle decompositions.  [PDF] [SLIDES]

A method which takes a decomposition of a graph into edge-disjoint cycles and produces a decomposition of a new graph into edge-disjoint cycles of the same lengths will be discussed. This method, called repacking, underpins much of the recent progress on cycle decomposition problems.

ANDREA BURGESS, Ryerson University
Orthogonally resolvable cycle decompositions  [PDF]

Two resolutions $\mathcal{R}$ and $\mathcal{S}$ of a design are said to be {\em orthogonal} if, for any resolution classes $R \in \mathcal{R}$ and $S \in \mathcal{S}$, $R$ and $S$ have at most one block in common. A design admitting a pair of orthogonal resolutions is said to be {\em doubly resolvable} or {\em orthogonally resolvable}. The existence of orthogonally resolvable Steiner triple systems, or Kirkman squares, was settled (with a finite number of possible exceptions) by Colbourn, Lamken, Ling and Mills. In this talk, we discuss the existence of further classes of orthogonally resolvable cycle decompositions.

PETER DANZIGER, Ryerson University
Bipartite 2-factorisations of complete multipartite graphs  [PDF] [SLIDES]

In the 1960's Ringel introduced the Oberwolfach problem: factor the complete graph, $K_n$, into an arbitrary specified 2-factor. Subsequently, a number of variations on this problem have been suggested, including specifying a number of 2-factors and an extension to the even case. We consider the case of a factorisation of the complete multipartite graph into bipartite 2-factors, and show that the obvious necessary conditions are sufficient, except that there is no factorisation of $K_{6,6}$ into the union of two disjoint $6$-cycles. Joint work with Darryn Bryant and William Petterson.

DANIEL HORSLEY, Monash University
Decomposing complete bipartite graphs into short cycles and related results  [PDF] [SLIDES]

In this talk I will discuss a result showing that a complete bipartite graph can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, the length of each cycle is at most the size of the smallest part, and the longest cycle is at most three times as long as the second longest. Using this result, it is possible to obtain results on decompositions of complete multipartite graphs into cycles of uniform even length and on (uniform length) even cycle systems containing subsystems.

BARBARA MAENHAUT, The University of Queensland
Cycle decompositions of complete multigraphs  [PDF] [SLIDES]

The multigraph version of Alspachâ€™s problem on cycle decompositions of complete graphs is to determine for each $\lambda$ and $n$, the set of all lists $m_1,m_2, \dots,m_t$ such that there exists a decomposition of the complete multigraph of order $n$ and multiplicity $\lambda$ into $t$ edge-disjoint cycles of lengths $m_1,m_2,\dots, m_t$. Some results on this problem will be discussed, including the solution to the problem in the case where all the cycles have the same length. This is joint work with Darryn Bryant, Daniel Horsley and Ben Smith.