Decomposition of Complete Graphs into Paths and Stars with Different Number of Edges

Let P n and K n respectively denote a path and complete graph on n vertices. By a { p H 1 , q H 2 } -decomposition of a graph G , we mean a decomposition of G into p copies of H 1 and q copies of H 2 for any admissible pair of nonnegative integers p and q , where H 1 and H 2 are subgraphs of G . In this paper, we show that for any admissible pair of nonnegative integers p and q , and positive integer n ≥ 4 , there exists a { p P 4 , q S 4 } -decomposition of K n if and only if 3 p + 4 q = ( n 2 ) , where S 4 is a star with 4 edges.