The Capture Time of the Hypercube

[摘要] 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 

[学科分类] 离散数学和组合数学

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