Double-Star Decomposition of Regular Graphs

الأصل · EN

A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k₁+ 1, k₂+ 1, 1,, 1) is denoted by Sₖ₁, ₖ₂. 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ₖ₁, ₖ₂ and Sₖ₁₋₁, ₖ₂, for all positive integers k₁ and k₂ such that k₁ + k₂= k.