### Abstract

Abstract. Let P_{k+1} denote a path of length k and let C _{k} denote a cycle of length k. As usual K_{n} denotes the complete graph on n vertices. In this paper we investigate decompositions of K_{n} into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing K_{n} into p copies of P _{5} and q copies of C_{4} for all possible values of p ≥ 0 and q ≥ 0.

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

Pages (from-to) | 257-270 |

Number of pages | 14 |

Journal | Ars Combinatoria |

Volume | 97 |

Publication status | Published - 2010 Oct 1 |

Externally published | Yes |

### Keywords

- Complete graph
- Cycle
- Graph decompositions
- Path

### ASJC Scopus subject areas

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Decompositions of complete graphs into paths and cycles'. Together they form a unique fingerprint.

## Cite this

Shyu, T. W. (2010). Decompositions of complete graphs into paths and cycles.

*Ars Combinatoria*,*97*, 257-270.