Double-Star Decomposition of Regular Graphs

Abstract

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,\dots ,1)$ is denoted by $S_{k_1,k_2}$. We study the edge-decomposition of regular 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 to $(2k+1)$-regular graphs, by showing that every $(2k+1)$-regular graph containing two disjoint perfect matchings is decomposed into $S_{k_1,k_2}$ and $S_{k_1-1,k_2}$, for all positive integers $k_1$ and $k_2$ such that $k_1+k_2=k$.

10 pages, 2 figures