Skip to main navigation Skip to Content
Paper IPM / M / 8317  


Abstract:  
A multicolored tree is a tree whose edges have different colors.
Brualdi and Hollingsworth [5] proved in any proper edge coloring
of the complete graph K_{2n}(n > 2) with 2n − 1 colors, there
are two edgedisjoint multicolored spanning trees. In this paper
we generalize this result showing that if (a_{1}, ... , a_{k}) is a
color distribution for the complete graph K_{n}, n ≥ 5,
such that 2 ≤ a_{1} ≤ a_{2} ≤ ... ≤ a_{k} ≤ (n + 1)/2, then there exist two edgedisjoint multicolored spanning
trees. Moreover, we prove that for any edge coloring of the
complete graph K_{n} with the above distribution if T is a
nonstar multicolored spanning tree of K_{n}, then there exists a
multicolored spanning tree T′ of K_{n} such that T and
T′ are edgedisjoint. Also it is shown that if K_{n}, n ≥ 6, is edge colored with k colors and k ≥ ((n−2)  2) +3 then there exist two edgedisjoint multicolored spanning
trees.
Download TeX format 

back to top 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir