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

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

MARCO BURATTI, Dipartimento di Matematica e Informatica, UniversitÃ  di Perugia, Italy
Cycle decompositions and their automorphism groups  [PDF] [SLIDES]

I would like to discuss the following problem.

\medskip\noindent {\it Determine for which pairs $(v,k)$ there exists a $k$-cycle system of order $v$ having an automorphism group of a given type (for instance cyclic) with a given action (for instance regular) on vertices}.

\medskip This problem is often hard but one can consider the following weaker form.

\medskip\noindent {\it Determine for which pairs $(v,k)$ there exists a $k$-cycle system of order $v$ having \underline{at least} one automorphism group (no matter of which type!) with a given action on the vertices}.

\medskip I will survey some results on the above problems.

DANNY DYER, Memorial University of Newfoundland
Graceful Labellings of Triangular Cacti  [PDF] [SLIDES]

A graceful labelling of a graph with $n$ edges is a vertex labelling using the elements $\{0, 1, \ldots, n\}$ where the the weight of an edge is the absolute difference between its two vertex labels, and all weights in $\{1,\ldots,n\}$ are achieved. We use Skolem sequences to gracefully label two families of triangular cacti, and then generalize these results. Finally, we use Rosa's well known method to obtain decompositions of complete graphs into triangular cacti. Joint work with Ian Payne, Nabil Shalaby, and Brenda Wicks.

HEATHER JORDON, Mathematical Reviews
Cycle Decompositions of Complete Graphs and Circulants  [PDF]

In this talk, we will discuss several different methods for decomposing complete graphs or almost complete graphs into cycles of a fixed length. We will also discuss how these techniques apply to circulant graphs.

SIBEL OZKAN, Gebze Institute of Technology, Turkey
On the Hamilton-Waterloo Problem with uniform cycle sizes  [PDF]

A $\{C_m^r,C_n^s\}$-decomposition of $K_v$ asks for a $2$-factorization of $K_v$, where $r$ of the 2-factors consists of $m$-cycles, and $s$ of the 2-factors consists of $n$-cycles. (For even $v$, it is a decomposition of $K_v - F$, where $F$ is a 1-factor.) This is a case of the Hamilton-Waterloo Problem(the HWP) with uniform cycle sizes $m$ and $n$. The HWP is an extension of the well-known Oberwolfach problem which asks for isomorphic 2-factors. Main focus of this talk will be on the HWP with uniform cycle sizes; some new results on the various lengths of cycles will be presented.

MATEJA SAJNA, University of Ottawa
On the directed Oberwolfach Problem with equal cycle length  [PDF] [SLIDES]

In this talk we present recent progress towards the determination of the necessary and sufficient conditions (on $m$ and $n$) for a complete symmetric digraph with $n$ vertices to admit a resolvable decomposition into directed cycles of length $m$. In the literature, these decompositions are also called {\em directed cycle systems} (with constant cycle length) and {\em Medelsohn designs} (with $\lambda=1$).

This is joint work with Andrea Burgess and Patrick Niesink.