Chasing robbers on random graphs: Zigzag theorem |
| |
| Authors: | Tomasz ?uczak Pawe? Pra?at |
| |
| Institution: | 1. Adam Mickiewicz University, Collegium Mathematicum, 61‐614 Poznań, Poland;2. Department of Mathematics, West Virginia University, Morgantown, West Virginia 26506‐6310 |
| |
| Abstract: | In this paper, we study the vertex pursuit game of Cops and Robbers where cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is the cop number of G. We present asymptotic results for the game of Cops and Robber played on a random graph G(n,p) for a wide range of p = p(n). It has been shown that the cop number as a function of an average degree forms an intriguing zigzag shape. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 |
| |
| Keywords: | random graphs complex networks vertex‐pursuit games Cops and Robbers domination adjacency property |
|
|
