Premium
Chasing a Fast Robber on Planar Graphs and Random Graphs
Author(s) -
Alon Noga,
Mehrabian Abbas
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21791
Subject(s) - mathematics , combinatorics , treewidth , planar graph , vertex (graph theory) , discrete mathematics , graph , constant (computer programming) , pathwidth , line graph , computer science , programming language
We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, that is, can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Letc ∞ ( G )denote the number of cops needed to capture the robber in a graph G in this variant, and lettw ( G ) denote the treewidth of G . We show that if G is planar thenc ∞ ( G ) = Θ ( tw ( G ) ) , and there is a polynomial‐time constant‐factor approximation algorithm for computingc ∞ ( G ) . We also determine, up to constant factors, the value ofc ∞ ( G )of the Erdős–Rényi random graph G = G ( n , p ) for all admissible values of p , and show that when the average degree is ω(1),c ∞ ( G )is typically asymptotic to the domination number.