Decompositions of complete graphs into paths and cycles

Research output: Contribution to journalArticle

18 Citations (Scopus)

Abstract

Abstract. Let Pk+1 denote a path of length k and let C k denote a cycle of length k. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decompositions of Kn 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 Kn into p copies of P 5 and q copies of C4 for all possible values of p ≥ 0 and q ≥ 0.

Original languageEnglish
Pages (from-to)257-270
Number of pages14
JournalArs Combinatoria
Volume97
Publication statusPublished - 2010 Oct 1
Externally publishedYes

    Fingerprint

Keywords

  • Complete graph
  • Cycle
  • Graph decompositions
  • Path

ASJC Scopus subject areas

  • Mathematics(all)

Cite this