### Abstract

Let C_{k} denote a cycle of length k and let S_{k} denote a star with k edges. As usual K_{n} denotes the complete graph on n vertices. In this paper we investigate decomposition of K_{n} into C_{l}'s and S_{k}'s, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of K_{n} into p copies of C_{4} and q copies of S_{4} if and only if 4(p + q) = q ≠ 1 if n is odd, and q ≥{3, n/2}if n is even.

Original language | English |
---|---|

Pages (from-to) | 301-313 |

Number of pages | 13 |

Journal | Graphs and Combinatorics |

Volume | 29 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2013 Jan 1 |

Externally published | Yes |

### Fingerprint

### Keywords

- Complete graph
- Cycle
- Graph decomposition
- Star

### ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics