Capturing the drunk robber on a graph

MaRDI QIDQ406701zbMATH OpenFDO

Authors Natasha Komarov, Peter Winkler

Publication date 9 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.4559, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random walkspursuit games on graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random walks on graphs (05C81) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: We show that the expected time for a smart "cop" to catch a drunk "robber" on an $n$-vertex graph is at most $n+mo(n)$. More precisely, let $G$ be a simple, connected, undirected graph with distinguished points $u$ and $v$ among its $n$ vertices. A cop begins at $u$ and a robber at $v$; they move alternately from vertex to adjacent vertex. The robber moves randomly, according to a simple random walk on $G$; the cop sees all and moves as she wishes, with the object of "capturing" the robber---that is, occupying the same vertex---in least expected time. We show that the cop succeeds in expected time no more than $n+mo(n)$. Since there are graphs in which capture time is at least $n-o(n)$, this is roughly best possible. We note also that no function of the diameter can be a bound on capture time.

Recommendations

• Chasing a drunk robber in many classes of graphs
• Some remarks on cops and drunk robbers
• Cop vs. gambler
• Cops and invisible robbers: the cost of drunkenness
• Cops and robbers in a random graph

Cites work

• scientific article; zbMATH DE number 3934148 (Why is no real title available?)
• A note on \(k\)-cop, \(l\)-robber games on graphs
• A probabilistic approach to Carne's bound
• Collisions Among Random Walks on a Graph
• Gibbs measures and dismantlable graphs
• Maximum diameter of regular digraphs
• Maximum hitting time for random walks on graphs
• On Cumulative Sums of Random Variables
• On cop-win graphs
• On the cop number of a graph
• Projective Planes
• The capture time of a graph
• Vertex-to-vertex pursuit in a graph

Cited in

(7)

• General cops and robbers games with randomness
• Tipsy cop and tipsy robber: collisions of biased random walks on graphs
• Cop vs. gambler
• Chasing a drunk robber in many classes of graphs
• Some remarks on cops and drunk robbers
• TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS
• Selfish cops and passive robber: qualitative games

This page was built for publication: Capturing the drunk robber on a graph

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