Packing balanced complete multipartite graphs with hexagons

Abstract

In this paper, we completely solve the problem of finding a maximum packing of any balanced complete multipartite graph K-m(n) with edge-disjoint 6-cycles, and minimum leaves are explicitly given. Subsequently, we also find a minimum covering of K-m(n).