Top

Journal of Combinatorial Optimization

Published in:

15-05-2019

The one-cop-moves game on planar graphs

Authors: Ziyuan Gao, Boting Yang

Published in: Journal of Combinatorial Optimization | Issue 3/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Cops and Robbers is a vertex-pursuit game played on graphs. In this game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’s positions. If a cop eventually occupies the same vertex as the robber, then the cops win; the robber wins if she can indefinitely evade capture. Aigner and Fromme established that in every connected planar graph, three cops are sufficient to capture a single robber. In this paper, we consider a recently studied variant of the cops and robbers game, alternately called the one-active-cop game, one-cop-moves game or the lazy cops and robbers game, where at most one cop can move during any round. We show that Aigner and Fromme’s result does not generalize to this game variant by constructing a connected planar graph on which a robber can indefinitely evade three cops in the one-cop-moves game.

previous article Mixed connectivity properties of random graphs and some special graphs

next article Tropical paths in vertex-colored graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

The same question was assigned to Shulang Lei and Rahim Ali in 2012 as their projects when they took the second author’s reading course.

Formal proofs establishing the one-cop-moves cop number of these graphs are usually quite tedious.

It is worth noting that a connected planar digraph based on the icosahedron was recently used by Loh and Oh (2017) to show that the cop number of directed planar graphs can exceed 3. Similarly, Abrahamsen et al. recently gave a geometric construction inspired by the dodecahedron to show that a man can escape two lions in a bounded area with rectifiable lakes.

The phrase “between the m-th round of the game and the n-th round of the game” will always mean “between the m-th round of the game and the nth-round of the game inclusive” (unless explicitly stated otherwise).

In order to reduce the number of cases in our proof, we choose to let the robber wait until a cop is exactly one edge away from her; by symmetrical considerations, it would suffice to assume that when the robber starts moving away from her current position o, there is exactly one cop occupying one of only three possible vertices adjacent to o (refer to \(p_1, p_2, p_3\) in Fig. 2).

If the conditions in Steps 2, 3 and 4 are not satisfied, then we use a strategy similar to the one given in the proof of Lemma 5.5 to move \(\gamma \) from a corner to another corner.

Abrahamsen M, Holm J, Rotenberg E, Wulff-Nilsen C. Best laid plans of lions and men. Preprint https://arxiv.org/pdf/1703.03687.pdf

Aigner M, Fromme M (1984) A game of cops and robbers. Discrete Appl Math 8:1–12MathSciNetCrossRef

Bal D, Bonato A, Kinnersley WB, Pralat P (2015) Lazy cops and robbers on hypercubes. Comb Probab Comput 24(6):829–837MathSciNetCrossRef

Bal D, Bonato A, Kinnersley WB, Pralat P (2016) Lazy cops and robbers played on random graphs and graphs on surfaces. Int J Comb 7(4):627–642MathSciNetMATH

Bonato A (2016) Conjectures on cops and robbers. In: Gera R, Hedetniemi S, Larson C (eds) Graph theory: favorite conjectures and open problems, vol 1. Springer, Basel, pp 31–42CrossRef

Bonato A, MacGillivray G (2017) Characterizations and algorithms for generalized cops and robbers games. Contrib Discrete Math 12(1):110–122MathSciNetMATH

Bonato A, Nowakowski R (2011) The game of cops and robbers on graphs. American Mathematical Society, ProvidenceCrossRef

Chung TH, Hollinger GA, Isler V (2011) Search and pursuit-evasion in mobile robotics. Auton Robots 31(4):299–316CrossRef

Clarke NE, MacGillivray G (2012) Characterizations of k-copwin graphs. Discrete Math 312:1421–1425MathSciNetCrossRef

Cormen TH, Leiserson CE, Rivest RL (2009) Introduction to algorithms. The MIT Press, CambridgeMATH

Isaza A, Lu J, Bulitko V, Greiner R (2008) A cover-based approach to multi-agent moving target pursuit. In: Proceedings of the 4th conference on artificial intelligence and interactive digital entertainment, pp 54–59

Lipton R, Tarjan R (1979) A separator theorem for planar graphs. SIAM J Appl Math 36:177–189MathSciNetCrossRef

Loh P, Oh S (2017) Cops and robbers on planar-directed graphs. J Graph Theory 86:329–340MathSciNetCrossRef

Moldenhauer C, Sturtevant NR (2009) Evaluating strategies for running from the cops. In: Proceedings of the 21st international joint conference on artificial intelligence, IJCAI’09, pp 584–589

Nowakowski R, Winkler P (1983) Vertex to vertex pursuit in a graph. Discrete Math 43:235–239MathSciNetCrossRef

Offner D, Okajian K (2014) Variations of cops and robber on the hypercube. Australas J Comb 59(2):229–250MathSciNetMATH

Quilliot A (1978) Jeux et pointes fixes sur les graphes. Thèse de 3ème cycle, Université de Paris VI, pp 131–145

Quilliot A (1985) A short note about pursuit games played on a graph with a given genus. J Comb Theory Ser B 38:89–92MathSciNetCrossRef

Sim KA, Tan TS, Wong KB (2017) Lazy cops and robbers on generalized hypercubes. Discrete Math 340:1693–1704MathSciNetCrossRef

Simard F, Morin M, Quimper C, Laviolette F, Desharnais J (2015) Bounding an optimal search path with a game of cop and robber on graphs. In: Principles and practice of constraint programming: 21st international conference, CP 2015, Cork, Ireland, Aug 31–Sept 4, 2015, proceedings. Springer, pp 403–418

Sullivan BW, Townsend N, Werzanski M. The \(3 \times 3\) rooks graph is the unique smallest graph with lazy cop number 3. Preprint arxiv:1606.08485

West DB (2000) Introduction to graph theory. Prentice Hall, Upper Saddle River

Yang B (2018) The one-cop-moves game on graphs of small treewidth (submitted)

Yang B, Hamilton W (2015) The optimal capture time of the one-cop-moves game. Theor Comput Sci 588:96–113MathSciNetCrossRef

Title: The one-cop-moves game on planar graphs
Authors: Ziyuan Gao
Boting Yang
Publication date: 15-05-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2021
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00417-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2021

Modified Greedy Heuristic for the one-dimensional cutting stock problem

A dynamic approach to detecting, eliminating and fixing memory leaks

The spectral radius and domination number in linear uniform hypergraphs

Big data driven urban railway planning: Shenzhen metro case study

On the price of anarchy of two-stage machine scheduling games

Tropical paths in vertex-colored graphs

Premium Partner