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

An (r, s)-tree is a connected, acyclic, bipartite graph withr light ands dark vertices. Uniform probability is assigned to the space,(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(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%.First author supported in part by grants from TGRC-KOSEF and BSRI 1409.