Cops and robbers on planar-directed graphs. (English) Zbl 1375.05172
Summary: M. Aigner and M. Fromme [Discrete Appl. Math. 8, 1–11 (1984; Zbl 0539.05052)] initiated the systematic study of the cop number of a graph by proving the elegant and sharp result that in every connected planar graph, three cops are sufficient to win a natural pursuit game against a single robber. This game, introduced by R. Nowakowski and P. Winkler [ibid. 43, 235–239 (1983; Zbl 0508.05058)], is commonly known as Cops and Robbers in the combinatorial literature. We extend this study to directed planar graphs, and establish separation from the undirected setting. We exhibit a geometric construction that shows that a sophisticated robber strategy can indefinitely evade three cops on a particular strongly connected planar-directed graph.
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C40 | Connectivity |
| 91A43 | Games involving graphs |
| 91A24 | Positional games (pursuit and evasion, etc.) |
References:
| [1] | M.Aigner and M.Fromme, A game of cops and robbers, Discrete Appl Math8 (1984), 1-12. · Zbl 0539.05052 |
| [2] | N.Alon and A.Mehrabian, Chasing a fast robber on planar graphs and random graphs, J Graph Theory78 (2015), 81-96. · Zbl 1305.05142 |
| [3] | B.Alspach, Searching and sweeping graphs, Le Matematiche59 (2004), 5-37. · Zbl 1195.05019 |
| [4] | W.Baird and A.Bonato, Meyniel’s conjecture on the cop number: a survey, J Comb3 (2012), 225-238. · Zbl 1276.05074 |
| [5] | A.Beveridge, A.Dudek, A.Frieze, and T.Müller, Cops and robbers on geometric graphs, Combin Probab Comput21(6) (2012), 816-834. · Zbl 1253.05104 |
| [6] | B.Bollobás, G.Kun, and I.Leader, Cops and robbers in a random graph, J Combin Theory Ser B103 (2013), 226-236. · Zbl 1261.05064 |
| [7] | A.Bonato and R.Nowakowski, The game of cops and robbers on graphs, Am Math Soc Student Math Library61 (2011). · Zbl 1298.91004 |
| [8] | F.Fomin and D.Thilikos, An annotated bibliography in guaranteed graph searching, Theoret Comput Sci399 (2008), 236-245. · Zbl 1160.68007 |
| [9] | P.Frankl, Cops and robbers in graphs of large girth and Cayley graphs, Discrete Appl Math17 (1987), 301-305. · Zbl 0624.05041 |
| [10] | P.Frankl, On a pursuit game on Cayley graphs, Combinatorica7 (1987), 67-70. · Zbl 0621.05017 |
| [11] | A.Frieze, M.Krivelevich, and P.Loh, Variations on cops and robbers, J Graph Theory69 (2012), 383-402. · Zbl 1243.05165 |
| [12] | G.Hahn, Cops, robbers, and graphs, Tatra Mt Math Publ36 (2007), 163-176. · Zbl 1164.05063 |
| [13] | R.Lipton and R.Tarjan, A separator theorem for planar graphs, SIAM J Appl Math36 (1979), 177-189. · Zbl 0432.05022 |
| [14] | L.Lu and X.Peng, On Meyniel’s conjecture of the cop number, J Graph Theory71 (2012), 192-205. · Zbl 1248.05121 |
| [15] | T.Łuczak and P.Prałat, Chasing robbers on random graphs: zigzag theorem, Random Struct Algor37 (2010), 516-524. · Zbl 1209.05226 |
| [16] | R.Nowakowski and P.Winkler, Vertex to vertex pursuit in a graph, Discrete Math43 (1983), 235-239. · Zbl 0508.05058 |
| [17] | P.Prałat and N.Wormald, Meyniel’s conjecture holds for random graphs, Random Struct Algor, to appear. · Zbl 1332.05096 |
| [18] | A.Quilliot, A short note about pursuit games played on a graph with a given genus, J Combin Theory Ser B38 (1985), 89-92. · Zbl 0586.90104 |
| [19] | A.Scott and B.Sudakov, A bound for the cops and robbers problem, SIAM J Discrete Math25 (2011), 1438-1442. · Zbl 1237.05132 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
