On double-star decomposition of 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, l d o t s, 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

2 k

-regular graph. In this paper, we extend this result to

(2 k + 1)

-regular graphs, by showing that every

(2 k + 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

.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: On double-star decomposition of graphs