In this talk, we consider the zero-visibility cops-and-robber game, which differs from the classical cops-and-robber game in one way: the robber is invisible. We show that the zero-visibility cop-number of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility cop-number can be bounded both above and below by positive multiples of the pathwidth.
We also consider the computational complexity aspects of the zero-visibility cops-and-robber game. On the one hand, we provide an algorithm that computes the zero-visibility cop-number of a tree in linear time. On the other hand, we show that the corresponding decision problem is NP-complete even for starlike graphs.
2017-06-20 14:00 ~ 15:00
Boting Yang, University of Regina
Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics