Back to Search
Start Over
COP AND ROBBER GAME AND HYPERBOLICITY.
- Source :
-
SIAM Journal on Discrete Mathematics . 2014, Vol. 28 Issue 4, p1987-2007. 21p. - Publication Year :
- 2014
-
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 < δ-hyperbolic with δ = O(s²). We also show that the dependency between S and s is linear if s - s' = Ω(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 δ-hyperbolic graph is cop-win for s = 2r and s' = r + 2δ 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 δ and s is linear for any s' < s. Using these results, we describe a simple constant-factor approximation of the hyperbolicity δ of a graph on n vertices in O(n²) time when the graph is given by its distance matrix. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 28
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 108625666
- Full Text :
- https://doi.org/10.1137/130941328