International Journal of Research and Scientific Innovation (IJRSI) | Volume VII, Issue I, January 2020 | ISSN 2321–2705
3-Factors of 3-Factorization of K(3,3,3,…,3) with n-Partite Sets for All Even Integers n≥2
M.D.M.C.P. Weerarathna, D.M.T.B. Dissanayake and A.A.I. Perera
Department of Mathematics, Faculty of Science, University of Peradeniya, Sri Lanka
Abstract:-A factorization of a graph G is a set of spanning sub-graph of G that are pairwise edge-disjoint and whose union is G. Factorization is one of the most active research areas in Graph Theory. In our previous work, 2-factors of 2-factorization of K(2,2,2,…,2) and K_(2r,2r,2r,⋯,2r) has been constructed by using degree factors. In this work, by considering degree factorization, a theorem has been proved to obtain 3-factors of 3-factorization of the complete multipartite graphs K(3,3,3,…,3).
Keywords: Complete n-partite graph, Factors, Factorization.
I. INTRODUCTION
Graph Theory is an important area in mathematics with many applications. A graph is a structure with vertices and edges. A simple graph G consists of a non-empty finite set V(G)of elements called vertices (or nodes) and a finite set E(G) of distinct unordered pairs of distinct elements of v(G) called edges [7]. The concept of factorization was introduced by Kirkman in 1847. In graph theory, a factor of a graph G is a spanning sub-graph of G which is not totally disconnected. A graph factorization of G is defined as a partition of edges of G into disjoint factors. Akiyama and Kano introduced two different types of factors which are called degree factors and component factors. A factor F described in terms of its degrees will be called a degree factor. On the other hand, if the factor is described using some other graphical method, it is called a component factor. The degree factors have been used for our research (A factor described in terms of its degrees).[1,4]
Application of graph factorization are involved in travelling salesman problem, coding theory, time scheduling in Multi-hop Networks, cooperative localization, Round-Robing tournaments etc.
Definition 1
A graph K(3,3,3,…,3) is n-partite if its vertices can be partitioned into n-sets (each with 3 points) in such a way that no edge joins vertices in the same set.
Definition 2
A complete n-partite graph is a simple n-partite graph in which each vertex in one partite set is adjacent to all the vertices in the other partite sets.[7]