Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T13:51:40.218Z Has data issue: false hasContentIssue false

The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]d

Published online by Cambridge University Press:  01 July 2016

Martin J. B. Appel*
Affiliation:
United Technologies Research Center
Ralph P. Russo*
Affiliation:
University of Iowa
*
∗ Postal address: United Technologies Research Center, East Hartford, CT 06108, USA.
∗∗ Postal address: Department of Statistics and Actuarial Science, University of Iowa, Iowa City, IA 52242, USA.

Abstract

On independent random points U 1 ,· ··,Un distributed uniformly on [0, 1]d , a random graph Gn (x) is constructed in which two distinct such points are joined by an edge if the l ∞-distance between them is at most some prescribed value 0 ≦ x ≦ 1. Almost-sure asymptotic rates of convergence/divergence are obtained for the maximum vertex degree of the random graph and related quantities, including the clique number, chromatic number and independence number, as the number n of points becomes large and the edge distance x is allowed to vary with n. Series and sequence criteria on edge distances {xn } are provided which guarantee the random graph to be empty of edges, a.s.

Information

Type
Stochastic Geometry and Statistical Applications
Copyright
Copyright © Applied Probability Trust 1997 

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.)

Article purchase

Temporarily unavailable