Published online by Cambridge University Press: 12 September 2008
Model 1. Consider the complete graph Kn, with vertex set [n] = {1, 2,…, n}, in which each edge e is assigned a length Xe. Colour the k shortest edges incident with each vertex green and the remaining edges blue. The graph made up of the green edges only, will be referred to as the k-th nearest neighbour graph. This graph has been studied in a variety of contexts both computational and statistical.