DECOMPOSING THE COMPLETE GRAPH INTO HAMILTONIAN PATHS (CYCLES) AND 3-STARS

Abstract

Let H be a graph. A decomposition of H is a set of edge-disjoint sub-graphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by S-k, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into alpha copies of Hamiltonian path (cycle) and beta copies of S-3.