Cop and Robber Game and Hyperbolicity

Abstract

In this note, we prove that all cop-win graphs $G$ in the game in which the robber and the cop move at different speeds $s$ and $s'$ with $s'<s$, are $\delta$-hyperbolic with $\delta=O(s^2)$. We also show that the dependency between $\delta$ and $s$ is linear if $s-s'=\Omega(s)$ and $G$ obeys a slightly stronger condition. This solves an open question from the paper [J. Chalopin et al., SIAM J. Discrete Math., 25 (2011), pp. 333--359]. Since any $\delta$-hyperbolic graph is cop-win for $s=2r$ and $s'=r+2\delta$ for any $r>0$, this establishes a new---game-theoretical---characterization of Gromov hyperbolicity. We also show that for weakly modular graphs the dependency between $\delta$ and $s$ is linear for any $s'<s$. Using these results, we describe a simple constant-factor approximation of the hyperbolicity $\delta$ of a graph on $n$ vertices in $O(n^2)$ time when the graph is given by its distance matrix.