Path and Cycle Decompositions

Abstract

A $G$-design is a partition of edge set of K_v in which each element induces a copy of G. The existence of G-designs with the additional property that they contain no proper subsystems has been previously settled when G is either K_3,or K_4-e by Rodger and Spicer. In this dissertation, we first solved the problem of G-designs with no subsystems where G = P_3, considering the problem for both designs and maximum packings with non-empty leaves. We then completely settled the problem for the general case of P_m-designs which contain no proper subsystems for every value of m and v.

We also solved another problem. A 4-cycle system is said to be diagonally switchable if each 4-cycle can be replaced by another 4-cycle obtained by replacing one pair of non-adjacent edges of the original 4-cycle by its diagonals so that the transformed set of 4-cycles forms another 4-cycle system. The existence of diagonally switchable 4-cycle system of K_v has already been solved. In this paper we give an alternative proof of this result and use the method to prove a new result for K_v-I, where I is any one factor of K_v.