Hostname: page-component-5cf477f64f-r2nwp Total loading time: 0 Render date: 2025-04-03T04:27:48.759Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Connectivity of Random k-th Nearest Neighbour Graphs

Published online by Cambridge University Press:  12 September 2008

Colin Cooper  and
Alan Frieze
Colin Cooper
Affiliation:
School of Mathematical Sciences, University of North London, London N7 8DB, UK
Alan Frieze
Affiliation:
Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 4 , Issue 4 , December 1995 , pp. 343 - 362
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N. and Spencer, J. H. (1991) The Probabilistic Method. John Wiley, Chichester.Google Scholar
[2]Bollobás, B. (1985) Random Graphs. Academic Press, New York.Google Scholar
[3]Erdős, P. and Rényi, A. (1961) On the strength of connectedness of a random graph. Acta Math. Acad. Sci. Hungar. 12 261–267.CrossRefGoogle Scholar
[4]Holst, L. (1992) On the number of vertices in the complete graph with a given vertex as nearest neighbour, in Frieze, A. M. and Luczak, T., eds., Random Graphs, Volume 2, John Wiley, Chichester, 91–99.Google Scholar
[5]McDiarmid, C. (1989) On the method of bounded differences. LMS Surveys in Combinatorics. Cambridge University Press, 148–184.Google Scholar
[6]Newman, C. M., Rinott, Y. and Tversky, A. (1983) Nearest neighbours and Voronoi regions in certain point processes. Advances in Applied Probability 15 726–751.CrossRefGoogle Scholar