We consider a complete graph on n vertices. Edges of the graph are prescribed random positive weights X1, X2, . . ., Xm. Here m = (n/2). We assume that these random variables are independent and have the common probability distribution with density function f (x), x \geq 0. Given a vertex v let T denote the shortest path tree with root v. Let T1, T2, . . . ⊂ T denote the trees that are obtained from T after removal of the root v. Let N1 \geq N2 \geq N3 \geq . . . denote (ordered) sequence of sizes of these trees. We study statistical properties of this sequence for various densities f and large n.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Please read the Copyright Notice in Journal Policy.