Vertex ordering and partitioning problems for random spatial graphs. (Q1884828)

For a finite graph of order \(n\) the vertices are labeled by integers \(1,\dots,n\) and any edge between \(i\) and \(j\) is given the weight \(i-j\) for \(i\) larger than \(j\). The labeling has to be chosen so that some functional of the edge weights is minimized. Such optimization problems are considered for various functionals when the vertices correspond to points randomly distributed on the \(d\)-dimensional unit cube, and the points are adjacent when they are at most a fixed threshold apart.