About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
The expected value of random minimal length spanning tree of a complete graph
Abstract
We consider the number c(n, m) of connected labeled graphs on n nodes and m edges and the intimately related object, the expected length of the minimal spanning tree of a complete graphs with random edge lengths. We use a very simple recursive procedure for computing the values of c(n, m) for computing the expected length of the minimal spanning tree exactly, under the uniform and the exponential distributions. Our computations are recursive, scale very well with the size of the problem, and we provide the values of the expected minimal length spanning trees for complete graphs K n with sizes n ≤ 45, extending recent results of Steele [Ste02], and Fill and Steele [FS04]. The main proof technique is based on introducing an artificial root to a graph and subsequently using a very simple inductive argument.