Decomposition of complete graphs into paths of length three and triangles

Research output: Contribution to journalArticle

8 Citations (Scopus)


Let P k+1 denote a path of length k and let C k denote a cycle of length k. A triangle is a cycle of length three. As usual K n denotes the complete graph on n vertices. It is shown that for all nonnegative integers p and q and for all positive integers n, K n can be decomposed into p copies of P 4 and q copies of C 3 if and only if 3(p + q) = e(K n), p ‡1 if n is odd, and p ≥ n/2 1/2 n is even.

Original languageEnglish
Pages (from-to)209-224
Number of pages16
JournalArs Combinatoria
Publication statusPublished - 2012 Oct 1
Externally publishedYes


ASJC Scopus subject areas

  • Mathematics(all)

Cite this