On the asymptotic behavior of the independence number of a random (n,n)-tree

An (r, s)-tree is a connected, acyclic, bipartite graph with r light and s dark vertices. Uniform probability is assigned to the space, Gamma(r,s), of (r,s)-trees. In this paper, we apply the probabilistic method to determine bounds for the vertex and the edge independence numbers for almost all (n,n)-trees in Gamma(n,n). Consequently, we find that for almost all (n, n)-trees the percentage of dark vertices in a maximum matching is at least 72%.