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 (2014)

  • Volume: 34, Issue: 1, page 113-125
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Atif A. Abueida, and Chester Lian. "On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges." Discussiones Mathematicae Graph Theory 34.1 (2014): 113-125. <http://eudml.org/doc/267952>.

@article{AtifA2014,
abstract = {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.},
author = {Atif A. Abueida, Chester Lian},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cycles; stars; graph-decompositions; graph decompositions},
language = {eng},
number = {1},
pages = {113-125},
title = {On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges},
url = {http://eudml.org/doc/267952},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Atif A. Abueida
AU - Chester Lian
TI - On the Decompositions of Complete Graphs into Cycles and Stars on the Same Number of Edges
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 113
EP - 125
AB - 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.
LA - eng
KW - cycles; stars; graph-decompositions; graph decompositions
UR - http://eudml.org/doc/267952
ER -

References

top
  1. [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. Zbl1224.05335
  2. [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] Zbl1032.05105
  3. [3] A. Abueida and M. Daven, Multidecompositions of the complete graph, Ars Combin. 72 (2004) 17-22. 
  4. [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. [5] A. Abueida and T. O’Neil, Multidecomposition of λKm into small cycles and claws, Bull. Inst. Combin. Appl. 49 (2007) 32-40. Zbl1112.05084
  6. [6] B. Alspach, Research problems, Problem 3, Discrete Math. 36 (1981) 333. doi:10.1016/S0012-365X(81)80029-5[Crossref] 
  7. [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] Zbl1023.05112
  8. [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] Zbl1205.05176
  9. [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. [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] Zbl1219.05146
  11. [11] T. Shyu, Decomposition of complete graphs into paths and cycles, Ars Combin. 97 (2010) 257-270. Zbl1249.05313
  12. [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. [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. Zbl0297.05143

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.