Cop and robber game and hyperbolicity

DOI10.1137/130941328MaRDI QIDQ5246100zbMATH OpenOpenAlexFDO

Authors J. Chalopin, Victor Chepoi, Panos Papasoglu, Timothée Pecatte

Publication date 17 April 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.3987

zbMATH Keywords

approximation algorithmscop and robber gamesdismantling orderingsGromov hyperbolicityweakly modular graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

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., Cop and robber games when the robber can hide and ride, SIAM J. Discr. Math. 25 (2011) 333-359). Since any delta-hyperbolic graph is cop-win for s=2r and s'=r+2delta 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.

Recommendations

• Gromov hyperbolicity and cop and robber game
• Cop and robber games when the robber can hide and ride
• Coarse geometry of the cops and robber game
• Hyperopic cops and robbers
• scientific article; zbMATH DE number 5241699

Cited in

(18)

• Obstructions to a small hyperbolicity in Helly graphs
• A simple approach for lower-bounding the distortion in any hyperbolic embedding
• The game of cops and eternal robbers
• Fellow travelers phenomenon present in real-world networks
• Mathematical properties on the hyperbolicity of interval graphs
• Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant
• On the hyperbolicity constant of circular-arc graphs
• Fast approximation and exact computation of negative curvature parameters of graphs
• Cop and robber games when the robber can hide and ride
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• Weakly Modular Graphs and Nonpositive Curvature
• Gromov hyperbolicity and cop and robber game
• Control sequencing in a game of identity pursuit-evasion
• The diameter of AT‐free graphs
• Coarse geometry of the cops and robber game
• Parameterized analysis of the cops and robber problem
• Compact metric spaces with infinite cop number
• Coarse cops and robber in graphs and groups

This page was built for publication: Cop and robber game and hyperbolicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5246100)