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

Document Type: Original Scientific Paper

Author

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

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}$‎. ‎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‎. ‎We present some necessary and some sufficient conditions for the existence of an $S_{1‎, ‎2}$-decomposition in cubic graphs‎.

Keywords

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.