ON THE EXPECTED NUMBER OF EDGES IN A MAXIMUM MATCHING OF AN (R,S)-TREE

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.