“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| 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 K2n(n > 2) with 2n − 1 colors, there
are two edge-disjoint multicolored spanning trees. In this paper
we generalize this result showing that if (a1, ... , ak) is a
color distribution for the complete graph Kn, n ≥ 5,
such that 2 ≤ a1 ≤ a2 ≤ ... ≤ ak ≤ (n + 1)/2, then there exist two edge-disjoint multicolored spanning
trees. Moreover, we prove that for any edge coloring of the
complete graph Kn with the above distribution if T is a
non-star multicolored spanning tree of Kn, then there exists a
multicolored spanning tree T′ of Kn such that T and
T′ are edge-disjoint. Also it is shown that if Kn, n ≥ 6, is edge colored with k colors and k ≥ ((n−2) || 2) +3 then there exist two edge-disjoint multicolored spanning
trees.
Download TeX format |
|
| back to top | |
