On edge-decomposition of cubic graphs into copies of the double-star with four edges

Abstract

A tree containing exactly two non-pendant vertices is called a double-star. Let $k_1$ and $k_2$ be two positive integers. The double-star with degree sequence $(k_1+1,k_2+1,1,\dots ,1)$ is denoted by $S_{k_1,k_2}$. If $G$ is a cubic graph and has an $S$-decomposition, for a double-star $S$, then $S$ is isomorphic to $S_{1,1}$, $S_{1,2}$ or $S_{2,2}$. It is known that a cubic graph has an $S_{1,1}$-decomposition if and only if it contains a perfect matching. In this paper we study the $S_{1,2}$-decomposition of cubic graphs. First, we present some necessary conditions for the existence of an $S_{1,2}$-decomposition in cubic graphs. Then we prove that every $\{C_3,C_5,C_7\}$-free cubic graph of order $n$ with $\alpha (G)=\frac{3n}{8}$ has an $S_{1,2}$-decomposition, where $\alpha (G)$ denotes the independence number of $G$. Finally, we obtain some results on the $S_{1,r-1}$-decomposition of $r$-regular graphs.

11 Pages, 4 Figures