On the Hamilton-Waterloo problem with two cycle sizes

Abstract

Çift döngülü Hamilton-Waterloo problemi, kısaca (n,m)-URD(v;r,s), v tek tamsayı iken tam çizge K_v'nin ya da v çift tamsayı olduğunda tam çizge eksi 1-faktör K_v-I'nın, parallel sınıflarından r tanesi n uzunluğunda, s tanesi ise m uzunluğunda döngülerden oluşan r+s=⌊(v-1)/2⌋ olacak şekilde bir çözülebilir döngü parçalanışının olup olmadığını inceler. Bu tezde ilk olarak, döngü uzunluklarının birinin 4, diğerinin m≥3 olacak şekilde bir tek tamsayı olduğu durum için, bir kaç olası istisnai durum dışında, bütün mümkün sonuçlar elde edilmiştir. Daha sonra döngü uzunluklarının m ve 4m olduğu durum için, yani bir döngü uzunluğu diğer döngü uzunluğunun dört katı olduğunda problem, çift m değerleri için tamamen, tek m değerleri için bir kaç olası istisnai durum dışında tamamen çözülmüştür.

The Hamilton-Waterloo problem with uniform cycle sizes, denoted by (n,m)-URD(v;r,s), asks for a resolvable cycle decomposition of the complete graph K_v (for odd v) or K_v minus a 1-factor (for even v) where r parallel classes consist of cycles of length n and s parallel classes consist of cycles of length m with r+s=⌊(v-1)/2⌋. In this dissertation, firstly, the Hamilton-Waterloo problem with 4-cycle and m-cycle factors for odd m≥3 is studied and all possible solutions with a few possible exceptions are determined. Then, all possible solutions for the m-cycle and 4m-cycle with a few possible exceptions when m is odd are obtained.