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

Main Subjects

References

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.
Mathematics Interdisciplinary Research
Volume 3, Issue 1
June 2018
Pages 67-74

Files

Share

How to cite

Statistics