Document Type

Article

Department

Mathematics (HMC)

Publication Date

2001

Abstract

A tree, being a connected acyclic graph, can be bicolored in two ways, which differ from each other by exchange of the colors. We shall say that a tree is equicolorable if these bicolorings assign the two colors to equal numbers of vertices. Labelled equicolored trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolorable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolorable is asymptotically just twice the probability that its vertices would be equicolored if they were assigned colors by independent unbiased coin flips. Our goal in this paper is the enumeration of unlabelled equicolorable trees (that is, trees up to isomorphism), both exactly (in terms of generating functions) and asymptotically. We treat both the rooted and unrooted versions of this problem and conclude that in either case the probability that a randomly chosen n-vertex unlabelled tree is equicolorable is asymptotically 1.40499... times as large as the probability that it would be equicolored if its vertices were assigned colors by independent unbiased coin flips.

Rights Information

© 2001 Society for Industrial and Applied Mathematics

Download

Share

COinS