Hyperopic cops and robbers (Q2328865): Difference between revisions

In the original version of Cops and Robbers game, visibility of the robber is there throughout the game. In this paper the authors considered a variant of this game where the cops have visibility of the robber only if he is not in their neighbor set. Such a variant of the original game is called as hyperopic cops and robber. If a cop is situated at every vertex of the corresponding graph, then the cops identify the robber in the first round and capture him in the next round. The minimum number of cops required to win in a graph $G$ is the hyperopic cop number $c_H(G)$ of the graph $G$. If $c_H(G) =k$, then $G$ is $k$-hyperopic cop-win. If $k =1$, then $G$ is hyperopic cop-win. The authors begin with a nice characterization result namely: $c_H(G) =1$ for a graph $G$ if and only if it is a tree. Second they give certain upper bounds for $c_H(G)$ depending on whether it has a cut vertex or is triangle free. Then they analyze $c_H(G)$ for graph $G$ with diameter 2 or at least 3. Also they determine $c_H(G)$ for planar graphs and countable graphs. They further listed a number of open problems on this topic for the serious readers. The proof techniques employed are novel and makes an interesting read.