Multidecomposition of complete graphs into cycles and claws
DOI:
https://doi.org/10.13069/jacodesmath.v13i2.271Keywords:
Graph decomposition, Complete graph, Cycle, StarAbstract
Let \( C_n \) and \( S_n \) respectively denote a cycle and star with \( n \) edges. Let \( K_n \) denote a complete graph on \( n \) vertices. In this paper, it is shown that for any non-negative integers \( \alpha \) and \( \beta \) and any positive integer \( n \geq 6 \), there exists a decomposition of \( K_n \) into \( \alpha \) copies of \( C_6 \) and \( \beta \) copies of \( S_3 \) if and only if \( 6\alpha + 3\beta = \binom{n}{2} \), \( \beta \neq 1,2 \) when \( n \) is odd, and \( \beta \geq \left\lceil \frac{n}{4} \right\rceil \) when \( n \) is even.
Received: 30 Dec 2022 | Accepted: 05 June 2025
Downloads
References
A. A. Abueida and M. Daven, Multidesigns for graph-pairs of order 4 and 5, Graphs Combin. 19 (2003) 433–447.
A. A. Abueida and M. Daven, Multidecompositions of the complete graph, Ars Combin. 72 (2004) 17–22.
A. A. Abueida and M. Daven, Multidecompositions of several graph products, Graphs Combin. 29 (2013) 315–326.
A. A. Abueida, M. Daven and K. J. Roblee, Multidesigns of the $\lambda$-fold complete graph-pairs of orders 4 and 5, Australas. J. Combin. 32 (2005) 125–136.
A. A. Abueida and T. O’Neil, Multidecomposition of $K_m(\lambda)$ into small cycles and claws, Bull. Inst. Combin. Appl. 49 (2007) 32–40.
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.
B. Alspach and H. Gavlas, Cycle decompositions of $K_n$ and $K_n-I$, J. Combin. Theory Ser. B 81 (2001) 77–99.
D. J. Ashe, H. L. Fu and C. A. Rodger, A solution to the forest leave problem for partial 6-cycles systems, Discrete Math. 281 (2004) 27–41.
R. Balakrishnan and K. Ranganathan, A Textbook of Graph theory, 2nd ed., Universitext, Springer New York, New York (2012).
F. Beggas, H. Haddad and H. Kheddouci, Decomposition of complete multigraphs into stars and cycles, Discuss. Math. Graph Theory 35 (2015) 629–639.
C. M. Fu, Yu-Fong Hsu and Ming-Feng Lee, Decomposition of complete graphs into 4-cycles and 3-stars, Utilitas Mathematica 106 (2018) 271–288.
C. M. Fu, Y. L. Lin, S.-W. Lo and Yu-F. Hsu, Decomposition of complete graphs into triangles and claws, Taiwanese J. of Math. 18 (2014) 1563–1581.
S. Jeevadoss and A. Muthusamy, Decomposition of complete bipartite graphs into paths and cycles, Discrete Math. 331 (2014) 98–108.
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.
H.-C. Lee, Multidecompositions of complete bipartite graphs into cycles and stars, Ars Combin. 108 (2013) 355–364.
H.-C. Lee and Y.-P. Chu, Multidecompositions of the balanced complete bipartite graphs into paths and stars, Int. Sch. Res. Not. 2013(1) (2013) 398473.
H.-C. Lee and J.-J. Lin, Decomposition of complete bipartite graphs with a 1-factor removed into cycles and stars, Discrete Math. 313 (2013) 2354–2358.
H. M. Priyadharsini and A. Muthusamy, $(G_{m}, H_{m})$-multifactorization of $\lambda K_{m}$, J. Combin. Math. Combin. Comput. 69 (2009) 145–150.
H. M. Priyadharsini and A. Muthusamy, $(G_{n}, H_{n})$-multidecomposition of $K_{n,n}(\lambda)$, Bull. Inst. Combin. Appl. 66 (2012) 42–48.
H. M. Priyadharsini and A. Muthusamy, $(K, H)$-multifactorization of $\lambda K_{m,m}$, AKCE Int. J. Graphs Comb. 10 (2013) 405–413.
M. Sajna, Cycle decompositions III: Complete graphs and fixed length cycles, J. Combin. Des. 10 (2002) 27–78.
T.-W. Shyu, Decompositions of complete graphs into paths and cycles, Ars Combin. 97 (2010) 257–270.
T.-W. Shyu, Decompositions of complete graphs into paths and stars, Discrete Math. 310 (2010) 2164–2169.
T.-W. Shyu, Decompositions of complete graphs into paths of length three and triangles, Ars Combin. 107 (2012) 209–224.
T.-W. Shyu, Decomposition of complete graphs into cycles and stars, Graphs Combin. 29 (2013) 301–313.
T.-W. Shyu, Decomposition of complete bipartite graphs into paths and stars with same number of edges, Discrete Math. 313 (2013) 865–871.
D. Sotteau, Decomposition of $K_{m,n}\left(K_{m,n}^{*}\right)$ into cycles (circuits) of length $2k$, J. Combin. Theory Ser. B 30 (1981) 75–81.
M. Tarsi, Decomposition of complete multigraph into stars, Discrete Math. 26 (1979) 273–278.
S. Yamamoto, H. Ikeda, S. Shige-ede, K. Ushio and N. Hamada, On claw decomposition of complete graphs and complete bipartite graphs, Hiroshima Math. J. 5 (1975) 33–42.
