Decomposing Kn∪P into triangles

Chin Mei Fu*, Hung-Lin Fu, C. A. Rodger

*Corresponding author for this work

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

In this paper, we extend the work on minimum coverings of Kn with triangles. We prove that when P is any forest on n vertices the multigraph G=Kn∪P can be decomposed into triangles if and only if three trivial necessary conditions are satisfied: (i) each vertex in G has even degree, (ii) each vertex in P has odd degree, and (iii) the number of edges in G is a multiple of 3. This result is of particular interest because the corresponding packing problem where the leave is any forest is yet to be solved. We also consider some other families of packings, and provide a variation on a proof by Colbourn and Rosa which settled the packing problem when P is any 2-regular graph on at most n vertices.

Original languageEnglish
Pages (from-to)131-136
Number of pages6
JournalDiscrete Mathematics
Volume284
Issue number1-3
DOIs
StatePublished - 6 Jul 2004

Keywords

  • Covering
  • Forest
  • Triple system

Fingerprint Dive into the research topics of 'Decomposing Kn∪P into triangles'. Together they form a unique fingerprint.

  • Cite this

    Fu, C. M., Fu, H-L., & Rodger, C. A. (2004). Decomposing Kn∪P into triangles. Discrete Mathematics, 284(1-3), 131-136. https://doi.org/10.1016/j.disc.2003.04.003