Geodesic
Decomposition of Complete Multigraphs Into Stars and Cycles
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 629-639.

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

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.
Keywords: graph decomposition, complete multigraph, stars, cycles 
@article{DMGT_2015_35_4_a2,
     author = {Beggas, Fairouz and Haddad, Mohammed and Kheddouci, Hamamache},
     title = {Decomposition of {Complete} {Multigraphs} {Into} {Stars} and {Cycles}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {629--639},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a2/}
}
TY  - JOUR
AU  - Beggas, Fairouz
AU  - Haddad, Mohammed
AU  - Kheddouci, Hamamache
TI  - Decomposition of Complete Multigraphs Into Stars and Cycles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 629
EP  - 639
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a2/
LA  - en
ID  - DMGT_2015_35_4_a2
ER  - 
%0 Journal Article
%A Beggas, Fairouz
%A Haddad, Mohammed
%A Kheddouci, Hamamache
%T Decomposition of Complete Multigraphs Into Stars and Cycles
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 629-639
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a2/
%G en
%F DMGT_2015_35_4_a2
Beggas, Fairouz; Haddad, Mohammed; Kheddouci, Hamamache. Decomposition of Complete Multigraphs Into Stars and Cycles. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 629-639. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a2/

[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

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

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

[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

[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

[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

[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

[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

[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

[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

[11] H.M. Priyadharsini and A. Muthusamy, (Gm,Hm)-multifactorization of λKm, J. Combin. Math. Combin. Comput. 69 (2009) 145-150.

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

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

[14] T.-W. Shyu, Decomposition of complete graphs into paths of length three and trian- gles, Ars Combin. 107 (2012) 209-224.

[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

[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

[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

[18] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979) 273-278. doi:10.1016/0012-365X(79)90034-7

[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

[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] 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.