Document Type

Article

Department

Mathematics (HMC)

Publication Date

1989

Abstract

This paper analyzes a process whereby the vertices of a graph are considered in a random sequence,and each considered vertex is “occupied” unless it or an adjacent vertex has previously been occupied. The process continues until no more vertices can be occupied, at which point the “jamming limit” has been reached. The case in which the graph is regular (so that every vertex has degree $d\geqq 2$ and has “few short cycles” is treated. In particular, the results apply to infinite regular trees, to finite graphs obtained from them by forming quotient graphs, and to random regular graphs.

It is shown that the probability that a vertex is occupied at the jamming limit tends to $(1 - 1/(d - 1)^{2/(d - 2)} )/2$ as the length of the shortest cycle through it tends to $\infty $. Also treated are graphs that have short cycles but for which every edge is in at most one cycle; in this way approximations are obtained to the occupancy probabilities for two-dimensional triangular, square and hexagonal lattices. Finally, a similar problem is treated in which edges rather than vertices are occupied, and the occupation of an edge prevents the later occupation of edges incident with it. In each case the solution gives the dynamic evolution of the occupancy probabilities, as well as their values at the jamming limit.

Rights Information

© 1989 Society for Industrial and Applied Mathematics

Download

Share

COinS