Geodesic
Decomposing the Complete Graph Into Hamiltonian Paths (Cycles) and 3-Stars
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 823-839.

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

Let H be a graph. A decomposition of H is a set of edge-disjoint subgraphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by Sk, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S3.
Keywords: decomposition, complete graph, Hamiltonian path, Hamiltonian cycle, star 
@article{DMGT_2020_40_3_a8,
     author = {Lee, Hung-Chih and Chen, Zhen-Chun},
     title = {Decomposing the {Complete} {Graph} {Into} {Hamiltonian} {Paths} {(Cycles)} and {3-Stars}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {823--839},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a8/}
}
TY  - JOUR
AU  - Lee, Hung-Chih
AU  - Chen, Zhen-Chun
TI  - Decomposing the Complete Graph Into Hamiltonian Paths (Cycles) and 3-Stars
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 823
EP  - 839
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a8/
LA  - en
ID  - DMGT_2020_40_3_a8
ER  - 
%0 Journal Article
%A Lee, Hung-Chih
%A Chen, Zhen-Chun
%T Decomposing the Complete Graph Into Hamiltonian Paths (Cycles) and 3-Stars
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 823-839
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a8/
%G en
%F DMGT_2020_40_3_a8
Lee, Hung-Chih; Chen, Zhen-Chun. Decomposing the Complete Graph Into Hamiltonian Paths (Cycles) and 3-Stars. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 823-839. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a8/

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

[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

[3] A. Abueida and M. Daven, Multidecompositons of the complete graph, Ars Combin. 72 (2004) 17–22.

[4] A. Abueida and M. Daven, Multidecompositions of several graph products, Graphs Combin. 29 (2013) 315–326. doi:10.1007/s00373-011-1127-x

[5] A. Abueida, M. Daven and K.J. Roblee, Multidesigns of the λ-fold complete graph for graph-pairs of order 4 and 5, Australas. J. Combin. 32 (2005) 125–136.

[6] A. Abueida and C. Hampson, Multidecomposition of Kn − F into graph-pairs of order 5 where F is a Hamilton cycle or an (almost) 1-factor, Ars Combin. 97 (2010) 399–416.

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

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

[9] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008) 7–20.

[10] F. Beggas, M. Haddad and H. Kheddouci, Decomposition of complete multigraphs into stars and cycles, Discuss. Math. Graph Theory 35 (2015) 629–639. doi:10.7151/dmgt.1820

[11] J. Bosák, Decompositions of Graphs (Kluwer, Dordrecht, Netherlands, 1990).

[12] D. Bryant, Packing paths in complete graphs, J. Combin. Theory Ser. B 100 (2010) 206–215. doi:10.1016/j.jctb.2009.08.004

[13] P. Hell and A. Rosa, Graph decompositions, handcuffed prisoners and balanced P -designs, Discrete Math. 2 (1972) 229–252. doi:10.1016/0012-365X(72)90005-2

[14] S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite graphs into paths and cycles, Discrete Math. 331 (2014) 98–108. doi:10.1016/j.disc.2014.05.009

[15] S. Jeevadoss and A. Muthusamy, Decomposition of product graphs into paths and cycles of length four, Graphs Combin. 32 (2016) 199–223. doi:10.1007/s00373-015-1564-z

[16] S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite multigraphs into paths and cycles having k edges, Discuss. Math. Graph Theory 35 (2015) 715–731. doi:10.7151/dmgt.1830

[17] R. Laskar and B. Auerbach, On decomposition of r-partite graphs into edge-disjoint Hamilton circuits, Discrete Math. 14 (1976) 265–268. doi:10.1016/0012-365X(76)90039-X

[18] H.-C. Lee, Multidecompositions of complete bipartite graphs into cycles and stars, Ars Combin. 108 (2013) 355–364.

[19] H.-C. Lee, Decomposition of the complete bipartite multigraph into cycles and stars, Discrete Math. 338 (2015) 1362–1369. doi:10.1016/j.disc.2015.02.019

[20] H.-C. Lee and Z.-C. Chen, Maximum packings and minimum coverings of multi-graphs with paths and stars, Taiwanese J. Math. 19 (2015) 1341–1357. doi:10.11650/tjm.19.2015.4456

[21] H.-C. Lee and C. Lin, Balanced star decompositions of regular multigraphs and λ-fold complete bipartite graphs, Discrete Math. 301 (2005) 195–206. doi:10.1016/j.disc.2005.04.023

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

[23] J.-J. Lin, Decompositions of multicrowns into cycles and stars, Taiwanese J. Math. 19 (2015) 1261–1270. doi:10.11650/tjm.19.2015.3460

[24] C. Lin, J.-J. Lin and T.-W. Shyu, Isomorphic star decomposition of multicrowns and the power of cycles, Ars Combin. 53 (1999) 249–256.

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

[26] H.M. Priyadharsini and A. Muthusamy, (Gm, Hm)-multidecomposition of Km,m(λ), Bull. Inst. Combin. Appl. 66 (2012) 42–48.

[27] T.-W. Shyu, Decomposition of complete graphs into paths and stars, Discrete Math. 310 (2010) 2164–2169. doi:10.1016/j.disc.2010.04.009

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

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

[30] T.-W. Shyu, Decomposition of complete graphs into cycles and stars, Graphs Combin. 29 (2013) 301–313. doi:10.1007/s00373-011-1105-3

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

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

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