  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, \ldots, 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$.
