On the directed Hamilton-Waterloo problem with two cycle sizes

Abstract

Bu tez bir $G$ çizgesinin bir $2$-faktörizasyonunu bulmak için gerekli şartları araştırmakta ve bu $2$-faktörizasyondaki faktörleri bulurken kullanılan yapıları ele almaktadır. Burada $G$'nin bir $2$-faktorizasyonu $G$'nin kenarlar kümesinin $2$-faktörlere parçalanışıdır ve bir $G$ çizgesinin bir $2$-faktörü, $G$'nin $2$-düzenli kapsayıcı bir alt çizgesidir. Kombinatoryal Tasarım Teorisi ve Çizge Teorisi alanlarındaki önemli konulardan biri, verilen bir çizgenin $2$-faktorizasyonun varlığını araştırmaktır. Ek olarak, çizgenin kenarlarının yönlü olması şartı eklediğinde $2$-faktorizasyon problemleri daha zor hale gelir. Bu tez yanlızca Oberwolfach Problemi, Hamilton-Waterloo Problemi ve bu problemlerin yönlü versiyonlarını içeren bazı $2$-faktorizasyon problemlerine odaklanmakla kalmayıp, aynı zamanda bu problemleri daha anlaşılır hale getirmek için bazı örnekler de vermektedir. Ayrıca, problemlerin çözümleri için gerekli şartlar incelenmiştir. Önce, ilgili problemler için literatürdeki sonuçlar ayrıntılı şekilde verilmiştir. Sonra, iki döngü uzunluklu Yönlü Hamilton-Waterloo problemininin çözümleri ele alınmış ve bunun için gerekli yapılar geliştirilmiştir. Yönlü Hamilton-Waterloo problemi, simetrik yönlü tam çizge $K_v^*$'ın iki izomorfik olmayan yönlü döngü faktörlere ayrışımını ister. Problemin tek tip versiyonunda, faktörler ya yönlü $m$-döngülerinden ya da $n$-döngülerinden oluşur ve o $\mathrm{HWP}^{*}(v; m^{r},$ $ n^{s})$ ile gösterilir; burada $r$ ve $s$ sırasıyla $r + s = v-1$ olacak şekilde yönlendirilmiş $m$-döngülerinin ve $n$-döngülerinin faktör sayısıdır. Bu tezde, bir $2$-faktorizasyon problemi ve bizim asıl odak noktamız olan Yönlü Hamilton-Waterloo Problemi tanıtıldıktan sonra, problemin çözümü için gerekli şartlar verilmiştir. Ayrıca problem, $(m, n)\in \{(4,6),(4,8),(4,12),(4,16),(6,12),(8,16)\}$ durumları için tamamen çözülmüştür. Dahası $v$'nin tek olduğu durumda ise $(m, n)\in \{(3,5),(3,15),(5,15)\}$ için birkaç olası istisna dışında çözülmüştür. Bu problemi belirli $m$ ve $n$ döngüler için çözmek demek, gerekli koşulları sağlayan olası bütün $r$ ve $s$ değerleri için probleme bir çözüm vermek demektir. Son olarak, $K_v^*$'ın izomorfik olmayan bazı özel faktörlere ayrışımının olabileceği birkaç olası istisna dışında gösterilmiştir: bu özel faktörler çift $m$ değerleri için, $K_v^*$'ın $K_2^*$ veya yönlü $m$-döngülerini, ve yönlü $m$-döngülerini veya $2m$-döngülerini içeren tek tip faktörleridir.This thesis studies the conditions for finding a $2$-factorization of a graph $G$ and handles the constructions used when finding the factors in this $2$-factorization. Herein, a $2$-factorization of a graph $G$ is a partition of the edge set of $G$ into $2$-factors that are $2$-regular spanning subgraphs of $G$. One of the important issues in the fields of Combinatorial Design Theory and Graph Theory is to explore the existence of a $2$-factorization of a given graph. In addition, when introducing directed edges in the graph, $2$-factorization problems become more challenging. This thesis not only focuses on some $2$-factorization problems involving the Oberwolfach Problem, the Hamilton-Waterloo Problem, and their directed versions but also gives some examples to make these problems more understandable. It also analyzes the necessary conditions for their solutions. First, the results from the literature on these problems are presented in detail. Then, the solutions to the Directed Hamilton-Waterloo Problem with two cycle sizes are given and the necessary constructions are developed. The Directed Hamilton-Waterloo Problem asks for directed cycle factorizations of the complete symmetric digraph $K_v^*$ into two non-isomorphic directed cycle factors. In the uniform version of the problem, factors consist of either directed $m$-cycles or $n$-cycles, and it is denoted by $\mathrm{HWP}^{*}(v; m^{r},$ $ n^{s})$ where $r$ and $s$ are the number of factors of directed $m$-cycles and $n$-cycles, respectively, such that $r + s = v-1$. In this thesis, after introducing the Directed Hamilton-Waterloo Problem, which is a $2$-factorization problem and our main focus, the necessary conditions for solving the problem are given. Also, the problem is completely solved for the factors with $(m, n)\in \{(4,6),(4,8),(4,12),$ $(4,16),(6,12),(8,16)\}$. Furthermore, the problem is solved for $(m, n)\in \{(3,5),(3,15),$ $(5,15)\}$ when $v$ is odd with a few possible exceptions. Solving this problem for certain $m$- and $n$-cycles means giving a solution to the problem for all possible values of $r$ and $s$ that satisfy the necessary conditions. Finally, it is shown, with a few possible exceptions, that $K_v^*$ can be factorized into some specific non-isomorphic factors, where these factors are uniform factors of $K_v^*$ involving $K_2^*$ or directed $m$-cycles, and directed $m$-cycles or $2m$-cycles for even $m$.