The cop density of a graph

Authors

  • Anthony Bonato
  • Geňa Hahn
  • Changping Wang

DOI:

https://doi.org/10.11575/cdm.v2i2.61984

Abstract

We consider the game of Cops and Robber played with infinitely many cops on countable graphs. We give a sufficient condition - the strongly $1$-e.c.\ property - for the cop number to be infinite. The cop density of a finite graph, defined as the ratio of the cop number and the number of vertices, is investigated. In the infinite case, the limits of the cop densities of chains of finite graphs are studied. For a strongly $1$-e.c.\ graph, any real number in $[0,1]$ may be realized as a cop density of the graph. We prove that if the cop number is infinite, then there is a chain with cop density $1;$ however, we give an example with cop number $1$ and cop density $1.$ We consider the cop density of finite connected graphs, and prove that for the $G(n,p)$ random graph, almost surely the cop density is concentrated around $\frac{\ln }{n}.$

Downloads

Published

2007-11-02

Issue

Section

Articles