Colour ratio in Prim's ranking of bipartite graphs

Abstract

We consider a complete bipartite graph of size $n$ endowed with i.i.d. uniform edge weights and run Prim's Algorithm to obtain a ranking of its vertices. Let ${\rho }_k^{(n)}$ be the proportion of black vertices among the first $k$ vertices in this ranking. We characterise the limit behaviour of ${\rho }_k^{(n)}$ as both $n$ and $k$ tend to infinity. Our results show that in general the limit of ${\rho }_k^{(n)}$, when existing, differs from the overall proportion of the black vertices in the graph.

34 pages and 1 figure