On minimum spanning trees for random Euclidean bipartite graphs

We consider the minimum spanning tree problem on a weighted complete bipartite graph K-nR,K- nB whose n= n(R) + n(B) vertices are random, i.i.d. uniformly distributed points in the unit cube in d dimensions and edge weights are the p-th power of their Euclidean distance, with p > 0. In the large n limit with n(R)/n -> alpha(R) and 0 < alpha(R) < 1, we show that the maximum vertex degree of the tree grows logarithmically, in contrast with the classical, non-bipartite, case, where a uniform bound holds depending on d only. Despite this difference, for p < d, we are able to prove that the total edge costs normalized by the rate n(1-p/d) converge to a limiting constant that can be represented as a series of integrals, thus extending a classical result of Avram and Bertsimas to the bipartite case and confirming a conjecture of Riva, Caracciolo and Malatesta.