On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges

• Autorzy: Atif A. Abueida , Chester Lian
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cycles; stars; graph-decompositions

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 1
• Strony: 113-125

Daty

wydano

2014-02-01

online

2014-02-14

Twórcy

autor

Atif A. Abueida

• Department of Mathematics University of Dayton 300 College Park, Dayton, OH 45469-2316

autor

Chester Lian

• Department of Mathematics University of Dayton 300 College Park, Dayton, OH 45469-2316

Bibliografia

• [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 [Crossref]
• [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.
• [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]
• [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]
• [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]
• [11] T. Shyu, Decomposition of complete graphs into paths and cycles, Ars Combin. 97 (2010) 257-270.
• [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.

Identyfikatory

DOI

10.7151/dmgt.1719