2-factorization of complete equipartite graphs with four and eight cycles

Abstract

K-düzenli bir çizge bütün derecelerin k olduğu bir çizgedir. 2-faktör ise G çizgesinin 2-düzenli kapsayıcı bir altçizgesidir. G'nin bir 2-faktorizasyonu, G'nin bütün kenarlarının 2- faktörlere parçalanışıdır. Eş parçalı bir çizge, köşe seti aynı kümedeki herhangi iki köşe bir kenar ile bağlı olmayacak şekilde eşit büyüklükte parçalara ayrılabilen bir çizgedir. u tane m elemanlı parçaya sahip tam eş parçalı çizge K(m:u) ile gösterilir ve farklı parçalardaki noktaların arasındaki bütün kenarları içerir. Bu tezde biz tam eş parçalı K(m:u) çizgesinin 4 ve 8 döngüleriyle 2-faktörizasyonunu bulacağız. Aslında bu K(m:u) için bir Hamilton-Waterloo problemidir. Hamilton-Waterloo problemi a1,a2, … ,ak döngü uzunluklarından oluşan r tane 2-faktörü ve b1,b2, … , bt döngü uzunluklarından oluşan s tane 2-faktörü olan tam Kv çizgesinin 2-faktörizasyonunu sorar. Biz bu problemi eş parçalı tam Km:u çizgelerine genelleyerek sırasıyla 4 ve 8 döngüleri içeren 2-faktörler üzerine çalışacağız.

A k-regular graph is a graph in which all the degrees are k. A spanning 2-regular subgraph of G is called a 2-factor in G. A 2-factorization of G is a decomposition of all the edges of G into edge-disjoint 2-factors. An equipartite graph is a graph whose vertex set can be partitioned into subsets of the same size such that no two vertices from the same subset are connected by an edge. The complete equipartite graph with u subsets of size m is denoted by K(m:u) and it contains every edge between vertices of different subsets. In this thesis we will find a 2-factorization of complete equipartite graph K(m:u) with four and eight cycles. In fact, this is a Hamilton-Waterloo problem for Km:u.