The Capture Time of the Hypercube

Electronic Journal Of Combinatorics

Anthony Bonato¹ 

关键词: Cops and Robbers;    hypercube;    coupon-collector problem;   

DOI  :  

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

来源: Electronic Journal Of Combinatorics

【 摘 要 】

In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the capture time of the $n$-dimensional hypercube is $\Theta (n\ln n)$. Our methods 

【 授权许可】

Others