CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Games on Graphs

FLORA BOWDITCH, University of Victoria
The Eternal Graph Colouring Game  [PDF]

The eternal graph colouring game is a dynamic version of graph colouring first introduced by Klostermeyer in 2014. In this two-player game, Player 1 tries to maintain a proper $k$-colouring of a graph $G$, while Player 2 requests vertices to change colour. In this talk, we analyze the minimum number of colours needed for Player 1 to maintain a proper colouring of $G$ "forever". We will give good bounds on this parameter, as well as observe some extremal cases. We conclude by relating this parameter to the fractional chromatic number.

Cops and Robbers on SAW orientations of the toroidal grid.  [PDF]

The game of "Cops and Robbers" is a pursuit-evasion game played on a graph. There are two players, one controls the cops and the other controls the robber, who take turns moving along edges of the graph. The goal of the cops is to capture the robber, which they accomplished by getting a cop to occupy the same vertex as the robber. The cop number of a graph $G$ is the minimum number of cops required to guarantee the robber's capture, and determining it is the main question regarding this game.

This game has been widely studied for the case of undirected graphs. In contrast, very little is known about the game played on digraphs. Recently, Hosseini and Mohar determined the cop number for some orientations toroidal grid. In this talk we will present bounds for the cop number for a more general family of orientations of this grid

JESSICA ENRIGHT, University of Stirling
Building a better mouse maze  [PDF]

Mouse Maze is a Flash game about Squeaky, a mouse who has to navigate a subset of the grid graph using a simple deterministic rule, which naturally generalises to a game on arbitrary graphs with some interesting chaotic-looking dynamics. We present efforts to generate graphs which effectively trap Squeaky in the maze for long periods of time, and some theoretical results bounding how long he can be trapped. We show that Squeaky can always escape the graph in finite time, but Squeaky can be trapped forever if he cannot count properly.

ASIYEH SANAEI, Kwantlen Polytechnic University
Containing Robber's Damage  [PDF]

In the game of Cops and Robber, we introduce \emph{damage number} of a graph which is, informally, the minimum number of distinct vertices the robber can visit before caught or contained by the cops. In copwin graphs, obviously the damage number is bounded by the capture time; however, for some classes the damage number is approximately half of the capture time. This motivates the idea of minimizing the damage or containing it. We show that in almost all graphs the damage number is less than $\frac{n}{2}$, confirm this result for graphs of small order and find or bound the damage number for classes of graphs.

Joint work with Danielle Cox at Mount Saint Vincent University.

MACKENZIE WHEELER, University of Victoria
Cops and Robbers on Infinite Graphs  [PDF]

Since the introduction of the vertex pursuit game Cops and Robbers in the early 1980’s, several characterizations of finite cop-win graphs have been known. One particular characterization of cop-win graphs is in terms of a vertex ordering called a cop-win ordering. This definition of a cop-win ordering for finite graphs does not directly translate to infinite graphs. We present a generalized definition of a cop-win ordering to infinite graphs. We show that every infinite graph that admits such an ordering is cop-win. Under the additional hypothesis that the number of paths between any two vertices of an infinite graph is finite, we show that an infinite graph $G$ is cop-win if and only if $G$ has a cop-win ordering.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology