Decomposition of complete graphs into paths and stars. (English) Zbl 1219.05146

Summary: Let \(P_{k+1}\) denote a path of length \(k\) and let \(S_{k+1}\) denote a star with \(k\) edges. As usual \(K_n\) denotes the complete graph on \(n\) vertices. In this paper we investigate the decomposition of \(K_n\) into paths and stars, and prove the following results.
Theorem A. Let \(p\) and \(q\) be nonnegative integers and let \(n\) be a positive integer. There exists a decomposition of \(K_n\) into \(p\) copies of \(P_{4}\) and \(q\) copies of \(S_{4}\) if and only if \(n\geq 6\) and \(3(p+q) = \binom n2\).
Theorem B. Let \(p\) and \(q\) be nonnegative integers, let \(n\) and \(k\) be positive integers such that \(n\geq 4k\) and \(k(p+q) = \binom n2\), and let one of the following conditions hold:
\(k\) is even and \(p \geq \frac k2\),
\(k\) is odd and \(p\geq k\).
Then there exists a decomposition of \(K_n\) into \(p\) copies of \(P_{k+1}\) and \(q\) copies of \(S_{k+1}\).


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
Full Text: DOI


[1] Abueida, A.A.; Daven, M., Multidesigns for graph-pairs of order 4 and 5, Graphs combin., 19, 433-447, (2003) · Zbl 1032.05105
[2] Abueida, A.A.; Daven, M., Multidecompositions of the complete graph, Ars combin., 72, 17-22, (2004) · Zbl 1071.05059
[3] Abueida, A.A.; Daven, M.; Roblee, K.J., Multidesigns of the \(\lambda\)-fold complete graph for graph-pairs of order 4 and 5, Australas. J. combin., 32, 125-136, (2005) · Zbl 1067.05054
[4] Abueida, A.A.; O’Neil, T., Multidecomposition of \(\lambda K_m\) into small cycles and claws, Bull. inst. combin. appl., 49, 32-40, (2007) · Zbl 1112.05084
[5] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan Press London · Zbl 1134.05001
[6] Lin, C.; Shyu, T.-W., A necessary and sufficient condition for the star decomposition of complete graphs, J. graph theory, 23, 361-364, (1996) · Zbl 0880.05069
[7] C.A. Parker, Complete bipartite graph path decompositions, Ph.D. Dissertation, Auburn University, Auburn, Alabama, 1998.
[8] Tarsi, M., Decomposition of complete multigraph into stars, Discrete math., 26, 273-278, (1979) · Zbl 0421.05016
[9] Tarsi, M., Decomposition of complete multigraph into simple paths: nonbalanced handcuffed designs, J. combin. theory ser. A, 34, 60-70, (1983) · Zbl 0511.05024
[10] Truszczyński, M., Note on the decomposition of \(\lambda K_{m, n}(\lambda K_{m, n}^\ast)\) into paths, Discrete math., 55, 89-96, (1985) · Zbl 0578.05054
[11] Yamamoto, S.; Ikeda, H.; Shige-ede, S.; Ushio, K.; Hamada, N., On claw decomposition of complete graphs and complete bipartie graphs, Hiroshima math. J., 5, 33-42, (1975) · Zbl 0297.05143
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.