A double-star is a tree with exactly two vertices of degree greater than 1. If T is a double-star where the two vertices of degree greater than one have degrees k1+1 and k2+1, then T is denoted by Sk1,k2 . In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star Sk,k−1 decomposes every 2k-regular graph that contains a perfect matching.
@article{bwmeta1.element.doi-10_7151_dmgt_1779,
author = {Saad I. El-Zanati and Marie Ermete and James Hasty and Michael J. Plantholt and Shailesh Tipnis},
title = {On Decomposing Regular Graphs Into Isomorphic Double-Stars},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {73-79},
zbl = {1308.05089},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1779}
}
Saad I. El-Zanati; Marie Ermete; James Hasty; Michael J. Plantholt; Shailesh Tipnis. On Decomposing Regular Graphs Into Isomorphic Double-Stars. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 73-79. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1779/
[1] P. Adams, D. Bryant and M. Buchanan, A survey on the existence of G-designs, J. Combin. Des. 16 (2008) 373-410. doi:10.1002/jcd.20170[Crossref] | Zbl 1168.05303
[2] D. Bryant and S. El-Zanati, Graph decompositions, in: Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz (Ed(s)), (2nd Ed., Chapman & Hall/CRC, Boca Raton, 2007) 477-485.
[3] S.I. El-Zanati, M.J. Plantholt and S. Tipnis, On decomposing even regular multi- graphs into small isomorphic trees, Discrete Math. 325 (2014) 47-51. doi:10.1016/j.disc.2014.02.011[Crossref] | Zbl 1288.05203
[4] J.A Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2013) #DS6. | Zbl 0953.05067
[5] R. Häggkvist, Decompositions of complete bipartite graphs, London Math. Soc. Lecture Note Ser. C.U.P., Cambridge 141 (1989) 115-147. | Zbl 0702.05065
[6] M.S. Jacobson, M. Truszczy´nski and Zs. Tuza, Decompositions of regular bipartite graphs, Discrete Math. 89 (1991) 17-27. doi:10.1016/0012-365X(91)90396-J[Crossref]
[7] F. Jaeger, C. Payan and M. Kouider, Partition of odd regular graphs into bistars, Discrete Math. 46 (1983) 93-94. doi:10.1016/0012-365X(83)90275-3[Crossref] | Zbl 0516.05052
[8] K.F. Jao, A.V. Kostochka and D.B. West, Decomposition of Cartesian products of regular graphs into isomorphic trees, J. Comb. 4 (2013) 469-490. | Zbl 1290.05108
[9] A. Kotzig, Problem 1, in: Problem session, Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XXIV (1979) 913-915.
[10] G. Ringel, Problem 25, in: Theory of Graphs and its Applications, Proc. Symposium Smolenice 1963, Prague (1964), 162.
[11] H. Snevily, Combinatorics of Finite Sets, Ph.D. Thesis, (University of Illinois 1991).