Geodesic
On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 113-125.

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

Let C_m and S_m denote a cycle and a star on m edges, respectively. We investigate the decomposition of the complete graphs, K_n, into cycles and stars on the same number of edges. We give an algorithm that determines values of n, for a given value of m, where K_n is C_m, S_m-decomposable. We show that the obvious necessary condition is sufficient for such decompositions to exist for different values of m.
Keywords: cycles, stars, graph-decompositions 
@article{DMGT_2014_34_1_a9,
     author = {Abueida, Atif A. and Lian, Chester},
     title = {On the {Decompositions} of {Complete} {Graphs} into {Cycles} and {Stars} on the {Same} {Number} of {Edges}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {113--125},
     publisher = {mathdoc},
     volume = {34},
     number = {1},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a9/}
}
TY  - JOUR
AU  - Abueida, Atif A.
AU  - Lian, Chester
TI  - On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 113
EP  - 125
VL  - 34
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a9/
LA  - en
ID  - DMGT_2014_34_1_a9
ER  - 
%0 Journal Article
%A Abueida, Atif A.
%A Lian, Chester
%T On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 113-125
%V 34
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a9/
%G en
%F DMGT_2014_34_1_a9
Abueida, Atif A.; Lian, Chester. On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 113-125. http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a9/

[1] A. Abueida, S. Clark and D. Leach, Multidecomposition of the complete graph into graph pairs of order 4 with various leaves, Ars Combin. 93 (2009) 403-407.

[2] A. Abueida and M. Daven, Multidesigns for graph-pairs of order 4 and 5, Graphs Combin. 19 (2003) 433-447. doi:10.1007/s00373-003-0530-3

[3] A. Abueida and M. Daven, Multidecompositions of the complete graph, Ars Combin. 72 (2004) 17-22.

[4] A. Abueida, M. Daven and K. Roblee, λ-fold multidesigns for graphs pairs on 4 and 5 vertices, Australas. J. Combin. 32 (2005) 125-136.

[5] A. Abueida and T. O’Neil, Multidecomposition of $λK_m$ into small cycles and claws, Bull. Inst. Combin. Appl. 49 (2007) 32-40.

[6] B. Alspach, Research problems, Problem 3, Discrete Math. 36 (1981) 333. doi:10.1016/S0012-365X(81)80029-5

[7] B. Alspach and H. Gavlas, Cycle decompositions of $K_n$ and $K_n − I$, J. Combin. Theory (B) 81 (2001) 77-99. doi:10.1006/jctb.2000.1996

[8] D. Bryant, D. Horsley, B. Maenhaut and B. Smith, Cycle decompositions of complete multigraphs J. Combin. Des. 19 (2011) 42-69. doi:10.1002/jcd.20263

[9] M. Šajna, Cycle decomposition III: complete graphs and fixed length cycles, J. Combin. Des. 10 (2002) 27-78. doi:10.1002/jcd.1027

[10] T. Shyu, Decomposition of complete graphs into paths and stars, Discrete Math. 310 (2010) 2164-2169. doi:10.1016/j.disc.2010.04.009

[11] T. Shyu, Decomposition of complete graphs into paths and cycles, Ars Combin. 97 (2010) 257-270.

[12] D. Sotteau, Decomposition of $K_{m,n}(K_{m,n}^*)$ into cycles (circuits) of length 2k, J. Combin. Theory (B) 30 (1981) 75-81. doi:10.1016/0095-8956(81)90093-9

[13] S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio, and N. Hamada, On claw-decomposition of complete graphs and complete bigraphs, Hiroshima Math. J. 5 (1975) 33-42.