Decomposition of Complete Multigraphs Into Stars and Cycles

Fairouz Beggas; Mohammed Haddad; Hamamache Kheddouci

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 629-639
  • ISSN: 2083-5892

Abstract

top
Let k be a positive integer, Sk and Ck denote, respectively, a star and a cycle of k edges. λKn is the usual notation for the complete multigraph on n vertices and in which every edge is taken λ times. In this paper, we investigate necessary and sufficient conditions for the existence of the decomposition of λKn into edges disjoint of stars Sk’s and cycles Ck’s.

How to cite

top

Fairouz Beggas, Mohammed Haddad, and Hamamache Kheddouci. "Decomposition of Complete Multigraphs Into Stars and Cycles." Discussiones Mathematicae Graph Theory 35.4 (2015): 629-639. <http://eudml.org/doc/276006>.

@article{FairouzBeggas2015,
abstract = {Let k be a positive integer, Sk and Ck denote, respectively, a star and a cycle of k edges. λKn is the usual notation for the complete multigraph on n vertices and in which every edge is taken λ times. In this paper, we investigate necessary and sufficient conditions for the existence of the decomposition of λKn into edges disjoint of stars Sk’s and cycles Ck’s.},
author = {Fairouz Beggas, Mohammed Haddad, Hamamache Kheddouci},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph decomposition; complete multigraph; stars; cycles},
language = {eng},
number = {4},
pages = {629-639},
title = {Decomposition of Complete Multigraphs Into Stars and Cycles},
url = {http://eudml.org/doc/276006},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Fairouz Beggas
AU - Mohammed Haddad
AU - Hamamache Kheddouci
TI - Decomposition of Complete Multigraphs Into Stars and Cycles
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 629
EP - 639
AB - Let k be a positive integer, Sk and Ck denote, respectively, a star and a cycle of k edges. λKn is the usual notation for the complete multigraph on n vertices and in which every edge is taken λ times. In this paper, we investigate necessary and sufficient conditions for the existence of the decomposition of λKn into edges disjoint of stars Sk’s and cycles Ck’s.
LA - eng
KW - graph decomposition; complete multigraph; stars; cycles
UR - http://eudml.org/doc/276006
ER -

References

top
  1. [1] A.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
  2. [2] A.A. Abueida and M. Daven, Multidecompositions of the complete graph, Ars Com- bin. 72 (2004) 17-22. 
  3. [3] A.A. Abueida and T. O’Neil, Multidecomposition of λKm into small cycles and claws, Bull. Inst. Combin. Appl. 49 (2007) 32-40. Zbl1112.05084
  4. [4] A.A. Abueida and C. Lian, On the decompositions of complete graphs into cycles and stars on the same number of edges, Discuss. Math. Graph Theory 34 (2014) 113-125. doi:10.7151/dmgt.1719[Crossref][WoS] Zbl1292.05211
  5. [5] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn − I, J. Combin. Theory, Ser. B 81 (2001) 77-99. doi:10.1006/jctb.2000.1996[Crossref] Zbl1023.05112
  6. [6] D. Bryant, D. Horsley, B. Maenhaut and B.R. Smith, Cycle decompositions of com- plete multigraphs, J. Combin. Des. 19 (2011) 42-69. doi:10.1002/jcd.20263[Crossref] Zbl1205.05176
  7. [7] V. Chitra and A. Muthusamy, Symmetric Hamilton cycle decompositions of complete multigraphs, Discuss. Math. Graph Theory 33 (2013) 695-707. doi:10.7151/dmgt.1687[WoS][Crossref] Zbl1297.05138
  8. [8] S. Cichacz, Decomposition of complete bipartite digraphs and even complete bipartite multigraphs into closed trails, Discuss. Math. Graph Theory 27 (2007) 241-249. doi:10.7151/dmgt.1358[Crossref] Zbl1133.05075
  9. [9] H.-C. Lee and J.-J. Lin, Decomposition of the complete bipartite graph with a 1- factor removed into cycles and stars, Discrete Math. 313 (2013) 2354-2358. doi:10.1016/j.disc.2013.06.014[WoS] Zbl1281.05109
  10. [10] Z. Liang and J. Guo, Decomposition of complete multigraphs into crown graphs, J. Appl. Math. Comput. 32 (2010) 507-517. doi:10.1007/s12190-009-0267-0[Crossref] Zbl1227.05193
  11. [11] H.M. Priyadharsini and A. Muthusamy, (Gm,Hm)-multifactorization of λKm, J. Combin. Math. Combin. Comput. 69 (2009) 145-150. Zbl1195.05061
  12. [12] M. Šajna, Cycle decompositions III: Complete graphs and fixed length cycles, J. Combin. Des. 10 (2002) 27-78. doi:10.1002/jcd.1027[Crossref] Zbl1033.05078
  13. [13] T.-W. Shyu, Decompositions of complete graphs into paths and cycles, Ars Combin. 97 (2010) 257-270. Zbl1249.05313
  14. [14] T.-W. Shyu, Decomposition of complete graphs into paths of length three and trian- gles, Ars Combin. 107 (2012) 209-224. 
  15. [15] T.-W. Shyu, Decomposition of complete graphs into cycles and stars, Graphs Com- bin. 29 (2013) 301-313. doi:10.1007/s00373-011-1105-3[Crossref] Zbl1263.05079
  16. [16] T.-W. Shyu, Decomposition of complete bipartite graphs into paths and stars with same number of edges, Discrete Math. 313 (2013) 865-871. doi:10.1016/j.disc.2012.12.020[Crossref] 
  17. [17] D. Sotteau, Decomposition of Km,n (K(*) m,n) into cycles (circuits) of length 2k, J. Combin. Theory, Ser. B 30 (1981) 75-81. doi:10.1016/0095-8956(81)90093-9[Crossref] 
  18. [18] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979) 273-278. doi:10.1016/0012-365X(79)90034-7[Crossref] 
  19. [19] M. Tarsi, Decomposition of a complete multigraph into simple paths: Nonbalanced handcuffed designs, J. Combin. Theory, Ser. A 34 (1983) 60-70. doi:10.1016/0097-3165(83)90040-7[Crossref] Zbl0511.05024
  20. [20] R.M.Wilson, Decomposition of complete graphs into subgraphs isomorphic to a given graph, in: Proceedings of the 5th British Combinatorial Conference, Util. Math., Winnipeg, Congr. Numer. 15 (1976) 647-659. 
  21. [21] 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.