Geodesic
On Decomposing Regular Graphs Into Isomorphic Double-Stars
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 1, pp. 73-79.

Voir la notice de l'article provenant de la source Library of Science

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 k_1+1 and k_2+1, then T is denoted by S_k_1,k_2. In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star S_k,k−1 decomposes every 2k-regular graph that contains a perfect matching.
Keywords: graph decomposition, double-stars 
@article{DMGT_2015_35_1_a5,
     author = {El-Zanati, Saad I. and Ermete, Marie and Hasty, James and Plantholt, Michael J. and Tipnis, Shailesh},
     title = {On {Decomposing} {Regular} {Graphs} {Into} {Isomorphic} {Double-Stars}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {73--79},
     publisher = {mathdoc},
     volume = {35},
     number = {1},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a5/}
}
TY  - JOUR
AU  - El-Zanati, Saad I.
AU  - Ermete, Marie
AU  - Hasty, James
AU  - Plantholt, Michael J.
AU  - Tipnis, Shailesh
TI  - On Decomposing Regular Graphs Into Isomorphic Double-Stars
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 73
EP  - 79
VL  - 35
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a5/
LA  - en
ID  - DMGT_2015_35_1_a5
ER  - 
%0 Journal Article
%A El-Zanati, Saad I.
%A Ermete, Marie
%A Hasty, James
%A Plantholt, Michael J.
%A Tipnis, Shailesh
%T On Decomposing Regular Graphs Into Isomorphic Double-Stars
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 73-79
%V 35
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a5/
%G en
%F DMGT_2015_35_1_a5
El-Zanati, Saad I.; Ermete, Marie; Hasty, James; Plantholt, Michael J.; Tipnis, Shailesh. On Decomposing Regular Graphs Into Isomorphic Double-Stars. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 1, pp. 73-79. http://geodesic.mathdoc.fr/item/DMGT_2015_35_1_a5/

[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

[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

[4] J.A Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2013) #DS6.

[5] R. Häggkvist, Decompositions of complete bipartite graphs, London Math. Soc. Lecture Note Ser. C.U.P., Cambridge 141 (1989) 115-147.

[6] M.S. Jacobson, M. Truszczyński and Zs. Tuza, Decompositions of regular bipartite graphs, Discrete Math. 89 (1991) 17-27. doi:10.1016/0012-365X(91)90396-J

[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

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

[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).