k-Factors of k-Factorization of K_(2^r,2^r,2^r,…,2^r ) with n-Partite Sets for k=1,2 and n≥2, n,r∈Z^+

International Journal of Research and Scientific Innovation (IJRSI) | Volume VI, Issue IX, September 2019 | ISSN 2321–2705

k-Factors of k-Factorization of K_{2^r,2^r,2^r,…,2^r} with n-Partite Sets for k=1,2 and n≥2, n,r∈Z⁺

M.D.M.C.P. Weerarathna, D.M.T.B. Dissanayake, D.G.S.D. Dehigama and A.A.I. Perera

Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka

Abstract: Graph factorization is one of the most flourishing areas in Graph Theory. Most of the research work on factorization is on complete graphs and complete bipartite graphs. In this research, complete k- partite graphs are considered. By considering degree factorization, two theorems have been proved to obtain factors of factorization of the complete multipartite graphs K_{(2,2,2,⋯,2)} and K_{(2^r,2^r,…,2^r )} with n partite sets where n≥2 and n,r∈Z⁺. Moreover, when n is even, 2-factors for 2-factorization of a complete multipartite graph of the form K_{(2,2,2,…,2)} have been obtained using the tournament scheduling technique by considering n partite sets as n teams.

Key words: Complete multipartite graphs, Factorization, Tournament scheduling technique

I. INTRODUCTION

Graph Theory has many applications in all disciplines. A graph consists of vertices and edges. A simple graph G is a pair (V(G),E(G)) where V(G) is a non empty finite set of elements called vertices and E(G) is a set of unorded pair of distinct elements of V(G) called edges [4]. A factor of a graph G is a spanning sub-graph of G which is not totally disconnected and a graph factorization of G is a partition of edges of G into disjoint factors. There are two different types of factors; degree-factors and component-factors. The notion of component-factors was introduced recently whereas graph factorization with respect to the degree has a history of more than one century and is one of the most active research areas in Graph theory. Applications of graph factorization are involved in Travelling salesman problem, Round-Robing tournaments, Kirkman’s school girl problem etc. The notion of factorization was introduced by Kirkman in 1847 and a result on a factorization of 1-factors was obtained by Reiss in 1859. A recent survey paper of factors and factorizations can be found in [3].

Read More