Geodesic
On Double-Star Decomposition of Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 835-840 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A tree containing exactly two non-pendant vertices is called a double-star. A double-star with degree sequence (k_1 + 1, k_2 + 1, 1, . . ., 1) is denoted by S_k_1,k_2. We study the edge-decomposition of graphs into double-stars. It was proved that every double-star of size k decomposes every 2k-regular graph. In this paper, we extend this result by showing that every graph in which every vertex has degree 2k + 1 or 2k + 2 and containing a 2-factor is decomposed into S_k_1,k_2 and S_k_1−1,k_2, for all positive integers k_1 and k_2 such that k_1 + k_2 = k.
Keywords: graph decomposition, double-stars, bipartite graph 
@article{DMGT_2017_37_3_a23,
     author = {Akbari, Saieed and Haghi, Shahab and Maimani, Hamidreza and Seify, Abbas},
     title = {On {Double-Star} {Decomposition} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {835--840},
     year = {2017},
     volume = {37},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a23/}
}
TY  - JOUR
AU  - Akbari, Saieed
AU  - Haghi, Shahab
AU  - Maimani, Hamidreza
AU  - Seify, Abbas
TI  - On Double-Star Decomposition of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 835
EP  - 840
VL  - 37
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a23/
LA  - en
ID  - DMGT_2017_37_3_a23
ER  - 
%0 Journal Article
%A Akbari, Saieed
%A Haghi, Shahab
%A Maimani, Hamidreza
%A Seify, Abbas
%T On Double-Star Decomposition of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 835-840
%V 37
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a23/
%G en
%F DMGT_2017_37_3_a23
Akbari, Saieed; Haghi, Shahab; Maimani, Hamidreza; Seify, Abbas. On Double-Star Decomposition of Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 835-840. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a23/

[1] J. Akiyama and M. Kano, Factors and Factorizations of Graphs (London, Springer, 2011). doi:10.1007/978-3-642-21919-1

[2] A. Bondy and U.S.R. Murty, Graph Theory (Graduate Texts in Mathematics, Springer, 2008).

[3] S.I. El-Zanati, M. Ermete, J. Hasty, M.J. Plantholt and S. Tipnis, On decomposing regular graphs into isomorphic double-stars, Discuss. Math. Graph Theory 35 (2015) 73–79. doi:10.7151/dmgt.1779

[4] M. 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

[5] 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

[6] A. Kötzig, Problem 1, in: Problem session, Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XXIV (1979) 913–915.

[7] G. Ringel, Problem 25, in: Theory of Graphs and its Applications, Proc. Symposium Smolenice 1963 (Prague, 1964), 162.