Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/130941328 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
cop and robber games,dismantling orderings,Gromov hyperbolicity,approximation algorithms,weakly modular graphs | Journal | 28 |
Issue | ISSN | Citations |
4 | 0895-4801 | 7 |
PageRank | References | Authors |
0.48 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jérémie Chalopin | 1 | 364 | 32.39 |
| Victor Chepoi | 2 | 708 | 77.46 |
| Panos Papasoglu | 3 | 13 | 2.10 |
| Timothée Pecatte | 4 | 16 | 2.89 |