On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges
Atif A. Abueida ; Chester Lian
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 113-125 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

Let Cm and Sm denote a cycle and a star on m edges, respectively. We investigate the decomposition of the complete graphs, Kn, 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 Kn is {Cm, Sm}-decomposable. We show that the obvious necessary condition is sufficient for such decompositions to exist for different values of m.

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:267952 
@article{bwmeta1.element.doi-10_7151_dmgt_1719,
     author = {Atif A. Abueida and Chester Lian},
     title = {On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {113-125},
     zbl = {1292.05211},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1719}
}

Atif A. Abueida; Chester Lian. On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 113-125. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1719/

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

[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 [Crossref] | Zbl 1032.05105

[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 λKm into small cycles and claws, Bull. Inst. Combin. Appl. 49 (2007) 32-40. | Zbl 1112.05084

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

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

[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[Crossref] | Zbl 1205.05176

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

[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[WoS][Crossref] | Zbl 1219.05146

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

[12] D. Sotteau, Decomposition of Km,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[Crossref]

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