Decomposition of complete graphs into 4-cycles and 3-stars

Abstract

Let Kn be a complete graph with n vertices, C_k denote a cycle of length fc, and Sk denote a star with k edges. We call C₄ a 4-cycle and S3 a 3-star. In this paper, we show that for any positive integer n > 6 and any nonnegative integers p and q, if 4p-f 3q = (n/2), q ≠ 1,2 for odd n and q > f (n/4) for even n) then there exists a decomposition of Kn into p copies of C₄ and q copies of £3. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.