All Title Author
Keywords Abstract


The cop density of a graph

Full-Text   Cite this paper   Add to My Lib

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}.$

Full-Text

comments powered by Disqus