The one-cop-moves game on planar graphs (extended abstract)

Introduction

Cops and Robbers, introduced by Nowakowski and Winkler [ 11 ] in 1983 and independently by Quillot [ 13 ] in 1978, is a game played on graphs, where a cop tries to capture a robber. The cop is rst placed on any vertex of the graph G, after which the robber chooses a starting vertex in G. The cop and robber then move in alternate turns, with the robber moving on odd turns and the cop moving on even turns. A round of the game consists of a robber's turn and the cop's subsequent turn. During every turn, each cop or robber either moves along an edge of G to a neighbouring vertex or stays put on his or her current vertex. Furthermore, both the cop and robber have perfect information about each other's positions at any point in the game. The cop wins the game if he eventually occupies the same vertex as the robber at some moment in the game; the robber wins if she can inde nitely avoid occupying any vertex containing the cop. A winning strategy for the cop on G is a set of instructions that, if followed, guarantees that the cop can win any game played on G, regardless of how the robber moves throughout the game. A winning strategy for the robber on G is de ned analogously.

Aigner and Frommer [ 1 ] generalised the original Cops and Robbers game by allowing more than one cop to play; we shall henceforth refer to this version of the game as the classical cops-and-robbers game. They associated to every nite graph G a parameter known as the cop number of G, denoted by c(G), which is the minimum number of cops needed for a cop winning strategy on G, and they showed that the cop number of every connected planar graph is at most 3. The cops-and-robbers game has attracted considerable attention from the graph theory community, owing in part to its connections to various graph parameters, as well as the large number of interesting combinatorial problems arising from the study of the cop number such as Meyniel's conjecture [ 4, 5 ], which states that for any graph G of order n, c(G) = O(pn). In addition, due to the relative simplicity and naturalness of the cops-and-robbers game, it has served as a model for studying problems in areas of applied computer science such as arti cial intelligence and robotics [ 7, 10 ].

This paper examines a variant of the classical cops-and-robbers game, known alternately as the one-active-cop game [ 12 ], lazy-cops-and-robbers game [ 2, 3, 15 ] or the one-cop-moves game [ 17 ]. The corresponding cop number of a graph G in this game variant is called the one-cop-moves cop number of G, and is denoted by c1(G). The one-cop-moves cop number has been studied for various special families of graphs [ 2, 12, 3, 15 ]. On the other hand, relatively little is known about the behaviour of the one-cop-moves cop number of connected planar graphs [ 5 ]. In particular, it is still open at present whether or not there exists an absolute constant k such that c1(G) k for all connected planar graphs G [ 3, 17 ]. Instead of attacking this problem directly, one may try to establish lower bounds on supfc1(G) : G is a connected planar graphg as a stepping stone. Note that the dodecahedron D is a connected planar graph with classical cop number equal to 3 [ 1 ]. Since any winning strategy for the robber on D in the classical cops-androbbers game can also be applied to D in the one-cop-moves game, it follows that c1(D) 3, and this immediately gives a lower bound of 3 on supfc1(G) : G is a connected planar graphg. To the best of our knowledge, there has hitherto been no improvement on this lower bound. Sullivan, Townsend and Werzanski [ 15 ] recently asked whether or not supfc1(G) : G is a connected planar graphg 4. The goal of the present work is to settle this question a rmatively: there is a connected planar graph whose one-cop-moves cop number is at least 4. Theorem 1. There is a connected planar graph D such that c1(D) 4.

Due to space constraints, we shall only describe the construction of the planar graph D and very brie y outline a strategy for evading three cops on D. 2

The construction of the planar graph D The construction of D starts with a dodecahedron D. We will add straight line segments on the surface of D to partition each pentagonal face of D into small polygons. For each pentagonal face U of D, we add 48 nested nonintersecting closed pentagonal chains, which are called pentagonal layers, such that each side of a layer is parallel to the corresponding side of U . Each vertex of a layer is called a corner of that layer. For convenience, the innermost layer is also called the 1-st layer in U and the boundary of U is also called the outermost layer of U or the 49-th layer of U . We add a vertex o in the centre of U and connect it to each corner of U using a straight line segment which passes through the corresponding corners of the 48 inner layers. For each side of the n-th layer (1 n 49), we add 2n + 1 internal vertices to partition the side path into 2n + 2 edges of equal length. Add a path of length 2 from the centre vertex o to every vertex of the innermost layer to partition the region inside the 1-st layer into 20 pentagons. Further, for each pair of consecutive pentagonal layers, say the n-th layer and the (n + 1)-st layer (1 n 48), add paths of length 2 from vertices of the n-th layer to vertices of the (n + 1)-st layer such that the region between the two layers is partitioned into 5(2n + 2) hexagons and 10 pentagons as illustrated in Figure 1. Let D be the graph consisting of all vertices and edges current on the surface of the dodecahedron D (including all added vertices and edges). Since D is constructed on the surface of a dodecahedron without any edge-crossing, D must be a planar graph. by U; U1; U2; : : : ; U10; U11 (see Figure 2).

For n 2 f1; : : : ; 49g, LU0;n denotes the n-th pentagonal layer of a pentagonal face U 0, starting from the innermost layer. The pentagonal faces of D are denoted 3

The robber's winning strategy

Let denote the robber. In Algorithm 1, we give a high-level description of 's winning strategy against three cops on D.

Algorithm 1: High-level strategy for

Since there are 12 pentagonal faces but only 3 cops, Step 1 of Algorithm 1 can be readily achieved. Let U denote the pentagonal face whose centre o is currently occupied by . The precise winning strategy for in Step 3 will depend on the relative positions of the cops when exactly one cop is 1 edge away from . The details of this phase of 's winning strategy can be described in three cases: (A) when three cops lie in U ; (B) when exactly one cop lies in U ; (C) when exactly two cops lie in U . These cases re ect three possible strategies for the cops: all three cops may try to encircle , or one cop may try to chase while the remaining two cops guard the neighbouring faces of U , or two cops may try to encircle while the remaining cop guards the neighbouring faces of U . 4

Concluding remarks

The present work established separation between the classical cops-and-robbers game and the one-cop-moves game on planar graphs by exhibiting a connected planar graph whose one-cop-moves cop number exceeds the largest possible classical cop number of connected planar graphs. We believe that this result represents an important rst step towards understanding the behaviour of the one-cop-moves cop number of planar graphs. It is hoped, moreover, that some of the proof techniques used in this work could be applied more generally to the one-cop-moves game played on any planar graph.

This work did not prove any upper bound for the one-cop-moves cop number of D; nonetheless, we believe that 4 cops are su cient for catching the robber on D. It should also be noted that the Planar Separator Theorem of Lipton and Tarjan [ 8 ] may be applied to show that the one-cop-moves cop number of every connected graph with n vertices is at most O(pn) (the proof is essentially the same as that in the case of planar directed graphs; see [9, Theorem 4.1]). The question of whether or not there exists a constant k such that c1(G) k for all connected planar graphs G [ 17 ] remains open. It is tempting to conjecture that such an absolute constant does exist.

References

1. M. Aigner and M. Fromme . A game of cops and robbers . Discrete Applied Mathematics 8 ( 1984 ): 1 { 12 .

2. D. Bal , A. Bonato , W. B. Kinnersley and P. Pralat . Lazy cops and robbers on hypercubes . Combinatorics Probability and Computing 24 ( 6 ): 829 { 837 , 2015 .

3. D. Bal , A. Bonato , W. B. Kinnersley and P. Pralat . Lazy cops and robbers played on random graphs and graphs on surfaces . International Journal of Combinatorics 7 ( 4 ): 627 { 642 , 2016 .

4. A. Bonato and R. Nowakowski . The Game of Cops and Robbers on Graphs. American Mathematical Society , Providence, 2011 .

5. A. Bonato ( 2016 ). Conjectures on cops and robbers . In Graph Theory: Favorite Conjectures and Open Problems - 1 (pages 31 { 42 ). Springer International Publishing.

6. N. E. Clarke and G. MacGillivray. Characterizations of k-copwin graphs . Discrete Mathematics 312 ( 2012 ): 1421 - 1425 .

7. A. Isaza , J. Lu , V. Bulitko and R. Greiner . A cover-based approach to multi-agent moving target pursuit . Proceedings of the 4th Conference on Arti cial Intelligence and Interactive Digital Entertainment , pages 54 { 59 , 2008 .

8. R. Lipton and R. Tarjan . A separator theorem for planar graphs . SIAM Journal on Applied Mathematics , 36 ( 1979 ): 177 - 189 .

9. P. Loh and S. Oh . Cops and robbers on planar directed graphs . Journal of Graph Theory , to appear.

10. C. Moldenhauer and N. R. Sturtevant . Evaluating strategies for running from the cops . IJCAI'09 , pages 584 { 589 , 2009 .

11. R. Nowakowski and P. Winkler . Vertex to vertex pursuit in a graph . Discrete Mathematics 43 ( 1983 ): 235 { 239 .

12. D. O ner and K. Okajian. Variations of Cops and Robber on the hypercube . Australasian Journal of Combinatorics 59 ( 2 ): 229 { 250 , 2014 .

13. A. Quilliot . Jeux et pointes xes sur les graphes . Thse de 3me cycle, Universit de Paris VI, 1978 , pages 131 - 145 .

14. A. Quilliot . A short note about pursuit games played on a graph with a given genus . Journal of Combinatorial Theory Series B 38 ( 1985 ): 89 { 92 .

15. B. W. Sullivan , N. Townsend and M. Werzanski . The 3 3 rooks graph is the unique smallest graph with lazy cop number 3 . Preprint. https://arxiv.org/abs/1606.08485.

16. D. B. West . Introduction to Graph Theory. Prentice Hall, 2000 .

17. B. Yang and W. Hamilton . The optimal capture time of the one-cop-moves game . Theoretical Computer Science 588 : 96 { 113 , 2015 .