CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Graph theory of Brian Alspach I
Responsable et président: Joy Morris (University of Lethbridge) et Mateja Sajna (University of Ottawa)

BRIAN ALSPACH, University of Newcastle
Pancyclicity and Cayley Graphs  [PDF]

We discuss pancyclic properties of Cayley graphs on abelian groups and generalized dihedral groups. Everything works as expected for Cayley graphs on abelian groups but some interesting problems arise for Cayley graphs on generalized dihedral groups.

LUIS GODDYN, Simon Fraser University
Pairity thrackles on surfaces  [PDF]

A graph drawn on a surface $X$ is a \emph{parity thrackle} if every pair of distinct edges properly cross an odd number of times. We show that every parity thrackle can be redrawn on $X$ so that every pair of edges cross exactly once. This extends work by Cairns-Nikolayevsky (2009) where $X$ is orientable, and relates to the Hanani-Tutte (1970) theorem regarding crossing numbers. This also leads to improved upper bounds on the edge density of classical a Conway (1969) thrackle. This is joint work with Yian Xu.

BARBARA MAENHAUT, The University of Queensland
Alspach's Cycle Decomposition Problem for Multigraphs  [PDF]

Alspach's cycle decomposition problem is to determine for each $n$, the set of all lists $m_1,m_2, \dots,m_t$ such that there exists a decomposition of the complete graph of order $n$ into $t$ edge-disjoint cycles of lengths $m_1,m_2,\dots, m_t$. A brief history of progress on this problem will be presented, culminating in its recent solution by Bryant, Horsley and Pettersson. The natural generalisation of this problem to cycle decompositions of the complete multigraph has also recently been solved and in this talk I will outline that solution. This is joint work with Darryn Bryant, Daniel Horsley and Ben Smith.

MATEJA SAJNA, University of Ottawa
Alspach's Conjecture for complete equipartite multigraphs: the amalgamation-detachment approach  [PDF]

In 1981, Alspach conjectured that a complete graph can be decomposed into $t$ cycles of lengths $c_1,c_2,\ldots,c_t$, respectively, whenever the obvious necessary conditions are satisfied. The conjecture has recently been proved by Bryant, Horsley, and Pettersson, and even more recently extended to complete multigraphs by Bryant, Horsley, Maenhaut, and Smith.

In this talk, using the amalgamation-detachment approach, we show that the complete equipartite multigraph $\lambda K_{n\times m}$ can be decomposed into cycles of lengths $c_1m,\dots,c_km$ whenever there exists a decomposition of $\lambda m K_n$ into cycles of lengths $c_1, \dots,c_k$.

This is joint work with Amin Bahmanian.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan