On Meyniel's conjecture of the cop number
Linyuan Lü, Xing Peng · Journal of Graph Theory · 2011
Abstract Meyniel conjectured that the cop number c ( G ) of any connected graph G on n vertices is at most for some constant C . In this article, we prove Meyniel's conjecture in special cases that G has diameter 2 or G is a bipartite graph of diameter 3. For general connected graphs, we prove , improving the best previously known upper‐bound O ( n / ln n ) due to Chiniforooshan.