Walkers on the Cycle and the Grid
Josep Dı́az, Xavier Pérez‐Giménez, Marı́a Serna, N. C. Wormald · SIAM Journal on Discrete Mathematics · 2008
We present a model of the establishment and maintenance of communication between mobile agents. We assume that the agents move through a fixed environment modeled by a motion graph and are able to communicate if they are within distance at most d of each other. As the agents move randomly, we analyze the evolution in time of the connectivity between a set of w agents, asymptotically for a large number N of vertices, when w also grows large. The particular topologies of the environment we study here are the cycle and the toroidal grid.