全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133