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

MaRDI QIDQ6265338zbMATH OpenFDO

Authors S. Akbari, Hamid Reza Maimani, Abbas Seify

Publication date 10 September 2015

Mathematics Subject Classification ID

Trees (05C05) Graph designs and isomorphic decomposition (05C51)

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,ldots,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)=frac3n8$ 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.

This page was built for publication: On edge-decomposition of cubic graphs into copies of the double-star with four edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6265338)