Almost Resolvable Maximum Packings of Complete Bipartite Graphs with 4-Cycles

Abstract

A packing of a complete bipartite graph K(m,n) with 4-cycles is a decomposition of K(m,n) into a collection C of edge-disjoint 4-cycles and a set of unused edges L referred to as the leave. If C is as large as possible (and L is as small as possible), then the packing is a maximum packing. An almost parallel class of a maximum packing is a largest possible set of vertex disjoint 4-cycles. In this paper we establish values of m and n for which a maximum packing of K(m,n) with 4-cycles may be resolved into almost parallel classes with the remaining cycles vertex disjoint.