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.
@article{bwmeta1.element.doi-10_7151_dmgt_1820,
author = {Fairouz Beggas and Mohammed Haddad and Hamamache Kheddouci},
title = {Decomposition of Complete Multigraphs Into Stars and Cycles},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {629-639},
zbl = {1327.05268},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1820}
}
Fairouz Beggas; Mohammed Haddad; Hamamache Kheddouci. Decomposition of Complete Multigraphs Into Stars and Cycles. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 629-639. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1820/
[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] | Zbl 1032.05105
[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. | Zbl 1112.05084
[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] | Zbl 1292.05211
[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] | Zbl 1023.05112
[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] | Zbl 1205.05176
[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] | Zbl 1297.05138
[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] | Zbl 1133.05075
[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] | Zbl 1281.05109
[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] | Zbl 1227.05193
[11] H.M. Priyadharsini and A. Muthusamy, (Gm,Hm)-multifactorization of λKm, J. Combin. Math. Combin. Comput. 69 (2009) 145-150. | Zbl 1195.05061
[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] | Zbl 1033.05078
[13] T.-W. Shyu, Decompositions of complete graphs into paths and cycles, Ars Combin. 97 (2010) 257-270. | Zbl 1249.05313
[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[Crossref] | Zbl 1263.05079
[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] 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] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979) 273-278. doi:10.1016/0012-365X(79)90034-7[Crossref]
[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] | Zbl 0511.05024
[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. | Zbl 0297.05143