Bi-cyclic decompositions of complete graphs into spanning trees

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We examine decompositions of complete graphs K4 k + 2 into 2 k + 1 isomorphic spanning trees. We develop a method of factorization based on a new type of vertex labelling, namely blended ρ-labelling. We also show that for every k ≥ 1 and every d, 3 ≤ d ≤ 4 k + 1 there is a tree with diameter d that decomposes K4 k + 2 into 2 k + 1 factors isomorphic to T.

Original languageEnglish (US)
Pages (from-to)1317-1322
Number of pages6
JournalDiscrete Mathematics
Volume307
Issue number11-12
DOIs
StatePublished - May 28 2007

Bibliographical note

Funding Information:
Research for this article was supported by the University of Minnesota Duluth Grant 177–1009.

Keywords

  • Graph factorization
  • Graph labelling
  • Spanning trees

Fingerprint Dive into the research topics of 'Bi-cyclic decompositions of complete graphs into spanning trees'. Together they form a unique fingerprint.

Cite this