Jh. Cho et Em. Palmer, ON THE EXPECTED NUMBER OF EDGES IN A MAXIMUM MATCHING OF AN (R,S)-TREE, International journal of computer mathematics, 56(1-2), 1995, pp. 39-50
An (r,s)-tree is a connected, acyclic, bipartite graph with r light an
d s dark vertices. In an earlier paper [Pa92] we investigated the edge
independence number of the superposition of 2 or more (r,s)-trees. He
re we focus on just one (r,s)-tree. We use three variable exponential
generating functions to establish a recurrence relation for the expect
ed value of the vertex independence number of (r,s)-trees, and hence t
hat of the edge independence number. Numerical values are calculated f
or small r and s. The data shows that for small (n,n)-trees the averag
e percentage of dark vertices in a maximum matching is over 87%. This
provides a basis for comparison with the asymptotic behavior of the ex
pectation, a topic to be explored in another paper.