Connected surveillance game (Q2345464)

The surveillance game is played on a graph \(G\) by two players, the surfer and the observer, as follows: Initially, the surfer stands on a marked vertex \(v\) of \(G\) with all other vertices of \(G\) being unmarked. Then the two players alternate with the observer marking \(k\) vertices of \(G\) and the surfer moving to a neighbour of its current position. The surfer wins if at some point it manages to move to an unmarked vertex. Otherwise the observer wins. The surveillance number \(\mathrm{sn}(G,v)\) of a graph \(G\) with initial vertex \(v\) is the smallest \(k\) such that the observer has a winning strategy. The game can be used to model web-page prefetching in which the web-browser aims to download web-pages before the surfer tries to access them. The connected surveillance game is a variant of the surveillance game in which the marked vertices need to always induce a connected subgraph of \(G\). The connected surveillance number \(\mathrm{csn(G,v)}\) is defined analogously. Of course, \(\mathrm{csn(G,v)} \geqslant \mathrm{sn}(G,v)\) but examples where \(\mathrm{csn(G,v)} > \mathrm{sn}(G,v)\) seem hard to construct. In this article the authors prove that \(\mathrm{csn(G,v)} \leqslant \sqrt{|V(G)|\mathrm{sn}(G,v)}\) and provide examples where \(\mathrm{csn(G,v)} = \mathrm{sn}(G,v) + 2\). They also investigate an online variant of the game in which at each step the observer only knows the neighbours of the marked vertices and not the whole graph. Furthermore they prove an NP-completeness result related to the game.