On the number of rainbow spanning trees in edge-colored complete graphs

Hung-Lin Fu, Yuan Hsun Lo, K. E. Perry*, C. A. Rodger

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


A spanning tree of a properly edge-colored complete graph, Kn, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if K2m is properly (2m−1)-edge-colored, then the edges of K2m can be partitioned into m rainbow spanning trees except when m=2. By means of an explicit, constructive approach, in this paper we construct ⌊6m+9∕3⌋ mutually edge-disjoint rainbow spanning trees for any positive value of m. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.

Original languageEnglish
Pages (from-to)2343-2352
Number of pages10
JournalDiscrete Mathematics
Issue number8
StatePublished - 1 Aug 2018


  • Complete graph
  • Edge-coloring
  • Rainbow spanning tree

Fingerprint Dive into the research topics of 'On the number of rainbow spanning trees in edge-colored complete graphs'. Together they form a unique fingerprint.

Cite this