Decomposition of Complete Multigraphs Into Stars and Cycles

• Autorzy: Fairouz Beggas , Mohammed Haddad , Hamamache Kheddouci
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph decomposition; complete multigraph; stars; cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 4
• Strony: 629-639

Daty

wydano

2015-11-01

online

2015-11-10

Twórcy

autor

Fairouz Beggas

• LIRIS UMR 5205, CNRS, University of Lyon, Claude Bernard Lyon 1 University 43 Bd du 11 Novembre 1918, F-69622, Villeurbanne, France

autor

Mohammed Haddad

• University 43 Bd du 11 Novembre 1918, F-69622, Villeurbanne

autor

Hamamache Kheddouci

• LIRIS UMR 5205, CNRS, University of Lyon, Claude Bernard Lyon 1 University 43 Bd du 11 Novembre 1918, F-69622, Villeurbanne, France

Bibliografia

• [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]
• [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[Crossref][WoS]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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[Crossref]
• [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[Crossref]
• [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]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1820