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 k1 and k2 be two positive integers‎. ‎The double-star with degree sequence (k1+1‎, ‎k2+1‎, ‎1‎, ...‎, ‎1) is denoted by Sk1‎, ‎k2‎. ‎It is known that a cubic graph has an S1,1-decomposition if and only if it contains a perfect matching‎. ‎In this paper‎, ‎we study the S1,2-decomposition of cubic graphs‎. ‎We present some necessary and some sufficient conditions for the existence of an S1,2-decomposition in cubic graphs‎.

Keywords

• ‎edge-decomposition‎
• ‎double-star‎
• ‎cubic graph‎
• ‎regular graph‎
• ‎bipartite graph