ON DOUBLE-STAR DECOMPOSITION OF GRAPHS

A tree containing exactly two non-pendant vertices is called a double star. A double-star with degree sequence (k(1) + 1, k(2) + 1, 1,..,1) is denoted by S-k1,(k2). We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into S-k1,(k2) and S-k1 - 1,(k2), for all positive integers k(1) and k(2) such that k(1) k(2) = k