Capturing the Drunk Robber on a Graph

Electronic Journal Of Combinatorics

Natasha Komarov¹ 

关键词: Graph theory;    Random walks;    Pursuit games on graphs;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

We show that the expected time for a smart "cop"' to catch a drunk "robber" on an $n$-vertex graph is at most $n + {\rm o}(n)$. More precisely, let $G$ be a simple, connected, undirected graph with distinguished points $u$ and $v$ among its $n$ vertices.

【 授权许可】

Others