CanaDAM 2021
En ligne, 25 - 28 mai 2021

Graph Searching
Org: Anthony Bonato (Ryerson University) et Nancy Clarke (Acadia University)

NANCY CLARKE, Acadia University
A variation of the Cops and Robber game with a new capture condition  [PDF]

Surrounding Cops and Robber is a variation of the game in which the cops win by occupying each of the robber's neighbouring vertices. The surrounding copnumber is analogous to the copnumber. We present a variety of results for this parameter, including exact values for several classes of graphs as well as more general bounds. Classes of interest include graph products, graphs arising from combinatorial designs, and generalized Petersen graphs. This is joint work with A.~Burgess, R.~Cameron, P.~Danziger, S.~Finbow, C.~Jones, and D.~Pike.

MELISSA HUGGAN, Ryerson University
Locating an invisible adversary  [PDF]

The localization game is a variant of Cops and Robbers where the robber is invisible and the cops use distance probes to determine the robber's location. The localization number of a graph is the minimum number of cops required to ensure the robber's capture. In this talk, we present bounds on the localization number of incidence graphs of certain classes of combinatorial designs. This is joint work with Anthony Bonato and Trent Marbach.

WILLIAM KINNERSLEY, University of Rhode Island
Infinitely fast robbers on grids  [PDF]

Recently, there has been considerable interest on variants of Cops and Robbers in which the robber is more mobile than the cops. In the infinite-speed robber variant, the robber may, on their turn, traverse an arbitrarily long cop-free path. In this talk, we present some recent work on this game. In particular, we determine the infinite-speed cop number of two-dimensional Cartesian grids up to a small additive constant, and we give asymptotic bounds for several families of grid-like graphs, including higher-dimensional Cartesian grids and hypercubes. This is joint work with Niko Townsend.

FIONN MC INERNEY, CISPA Helmholtz Center for Information Security
Eternal Domination in D-Dimensional Grids  [PDF]

In eternal domination, a vertex is attacked at each turn, and a team of guards must move a guard to that vertex to defend it. The guards may only move to adjacent vertices on their turn. The eternal domination number $\gamma^{\infty}_{all}$ of a graph is the minimum number of guards required to defend against an infinite sequence of attacks. I show a technique to prove that $\gamma_{all}^{\infty}(G)=\gamma(G)+o(\gamma(G))$ for all graphs $G\in \mathcal{F}$, where $\mathcal{F}$ is a large family of $D$-dimensional grids which are supergraphs of the $D$-dimensional Cartesian grid and subgraphs of the $D$-dimensional strong grid.

BOJAN MOHAR, Simon Fraser University
Cops and robbers on surfaces  [PDF]

Pursuit-evasion games in subspaces of the Euclidean space have been studied extensively, especially in the framework of differential games. However, differential pursuit-evasion games behave differently from the combinatorial game of Cops and Robbers played on graphs. The speaker will discuss how to define the game of cops and robbers on a Riemannian surface with intention to preserve all the beauty of the game played on graphs.