On Edge-Decomposition of Cubic Graphs into Copies of the Double-Star with Four Edges‎

Document Type : Original Scientific Paper


Department of Sciences, Shahid Rajaei Teacher Training University, Tehran, I. R. Iran


‎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‎.


Main Subjects

1. J. Barát, D. Gerbner, Edge-decomposition of graphs into copies of a tree with four edges, Electron. J. Combin. 21 (1) (2014) Paper 1.55, 11 pp.
2. J. Bensmail, A. Harutyunyan, T. -N. Le, M. Merker, S. Thomassé, A Proof of the Barát-Thomassen Conjecture, arXiv:1603.00197.
3. A. Bondy, U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, Springer, New York, (2008).
4. A. Kötzig, Aus der theorie der endlichen regulären graphen dritten und vierten grades, Časopis. Pěst. Mat. 82 (1957) 76–92.
5. C. Thomassen, Edge-decompositions of highly connected graphs into paths, Abh. Math. Semin. Univ. Hambg. 78 (2008) 17–26.
6. C. Thomassen, Decompositions of highly connected graphs into paths of length 3, J. Graph Theory 58 (2008) 286–292.