Maximum Spanning Trees of Random Geometric Graphs With Independent Edge Weights

Abstract

In this paper, we study maximum weight spanning trees of the random geometric graph (RGG)~\(G\) formed by~\(n\) vertices where each edge is independently either open or closed with a certain probability and is also equipped with an independent random positive weight. We use segmentation and iterative path construction to obtain deviation bounds for the order of growth of the maximum weight of a spanning tree in terms of an inverse of the edge weight complementary cumulative distribution function (ccdf) and also illustrate our results for the special cases of power law and exponential decay. We then use martingale difference methods to individually estimate the variance contribution due to randomness in vertex locations and edge states/weights and determine sufficient conditions for~\(L^2-\)convergence of the maximum weight, appropriately scaled and centred.