Certain Resolvable Directed Cycle Decompositions of Directed Graphs

Abstract

In this thesis, we address two problems in cycle decompositions. In the first problem, we resolve the last outstanding case of the directed Oberwolfach problem with tables of uniform length. More specifically, we address the case with two tables of equal odd length. To do so, we construct a resolvable decomposition of the complete symmetric directed graph into two directed cycles of the same odd length. This affirms a conjecture of Burgess and Šajna (2014).

In the second problem addressed in this thesis, we partially solve a conjecture on directed cycle decompositions of products of directed graphs. This conjecture stipulates that, given two directed graphs G and H that both admit a decomposition into directed hamiltonian cycles, the wreath (lexicographic) product of G with H can also be decomposed into directed hamiltonian cycles. This conjecture has been shown to be true when |V (G)| is odd and |V (H)|> 2 by Ng (1998). In this thesis, we assume that |V (G)| is even and show that this conjecture is true if |V (H)| is odd and |V (H)|> 3, or |V (H)| is even, |V (H)|> 2, and G is not a directed cycle. In addition, we show that, if G is a directed cycle, where |V (G)|> 2, and H is either a directed m-cycle with m ⩾ 4 even or H is the complete symmetric directed graph on m vertices such that m ⩾ 3, then the aforementioned conjecture is also true. Lastly, we show that this conjecture is false when G is a directed cycle of even length and H is a directed cycle of length 2 or 3.