=Paper=
{{Paper
|id=Vol-1949/AUXICTCSpaper10
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1949/AUXICTCSpaper10.pdf
|volume=Vol-1949
}}
==None==
https://ceur-ws.org/Vol-1949/AUXICTCSpaper10.pdf
The one-cop-moves game on planar graphs
(extended abstract)
Ziyuan Gao and Boting Yang
Department of Computer Science
University of Regina, Regina, SK, Canada
Email: {gao257,boting}@cs.uregina.ca
1 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 first 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 indefinitely 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
defined 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
finite 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( n). 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 artificial 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
sup{c1 (G) : G is a connected planar graph} 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-and-
robbers 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 sup{c1 (G) :
G is a connected planar graph}. 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 sup{c1 (G) : G is a connected planar graph} ≥ 4.
The goal of the present work is to settle this question affirmatively: 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 briefly 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
Fig. 1. Two innermost and two outermost pentagonal layers of a pentagonal face.
is constructed on the surface of a dodecahedron without any edge-crossing, D
must be a planar graph.
For n ∈ {1, . . . , 49}, LU 0 ,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
by U, U1 , U2 , . . . , U10 , U11 (see Figure 2).
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 γ
1 γ picks the centre of a pentagonal face that is free of cops. Let U be this face.
2 γ stays at the centre o of U until there is exactly one cop that is 1 edge away
from γ.
3 γ does one of the following depending on the cops’ positions and strategy: (i) she
moves to the centre of a pentagonal face U 0 , which may or may not be U ,
without being caught at the end of a round, or (ii) she oscillates back and forth
along an edge for the rest of the game without being caught.
0
4 If, in Step 3, γ does (i), then set U ←− U and go back to Step 2.
Fig. 2. 12 pentagonal faces of D, labelled U, U1 , . . . , U11 .
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 reflect 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 first 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 sufficient 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( n) (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 Artificial 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. Offner 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 fixes 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.