Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

Cops-and-Robbers: Remarks and Problems

Michel Boyer1, Sif El Harti1, Amal El Ouarari1, Robert Ganian2, Tomas Gavenéiak3, Gefia Hahn1, Carsten Moldenaue4, Ignaz Rutter5, Benoit Thériault1, Martin Vatshelle6
1Département d’informatique et de recherche opérationnelle, Université de Montréal, C.P. $126 succursale Centre-ville, Montréal, QC, Canada, HSC $J7
2Faculty of Informatics, Masaryk University, Botanickd 68a, 60200 Brno Czech Republic
3Department of Applied Mathematics and Institute for Theoretical! Computer Science (ITI), Charles University, Malostranskridm. 25, 118 00 Prahe 1, Czech Republic
4Humboldt-Universitdt zu Berlin, Institut fir Informatik, D-10099 Berlin, Germany 4Karlsruhe Institute of Technology (KIT), Institute of Theoretical Informatics, D-76128 Karlsruhe, Germany
5Karlsruhe Institute of Technology (KIT), Institute of Theoretical Informatics, D-76128 Karlsruhe, Germany
6University of Bergen, Department of Informatics, pb. 7809, 5020 Bergen, Norway
  • Published: 31/05/2013

Abstract

We explore cops-and-robbers games in several directions, giving partial results in each and refuting two reasonable conjectures. We close with some open problems.

Keywords: cops-and-robbers, graph, directed graph, tournament, reflexive graph, graph searching, optimal game, constrained game
Citation
Michel Boyer, Sif El Harti, Amal El Ouarari, Robert Ganian, Tomas Gavenéiak, Gefia Hahn, Carsten Moldenaue, Ignaz Rutter, Benoit Thériault, Martin Vatshelle. Cops-and-Robbers: Remarks and Problems[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 085. 141-159. .