2026 CMS Summer Meeting

Saint John, June 5 - 8, 2026

Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Problems in Graph Searching
Org: Beth Ann Austin (Memorial University), Iain Beaton (Acadia University) and Danielle Cox (Mount Saint Vincent University)
[PDF]

BETH ANN AUSTIN, Memorial University Calling in reinforcements to limit damage [PDF]

The damage number of a graph, introduced by Cox and Sanaei, is the minimum number of distinct vertices a robber can visit without capture. We consider the variant where multiple cops are allowed, and give results on several families of graphs. This is joint work with Danny Dyer and Melissa Huggan.

GRIFFIN BARTLETT, Memorial University of Newfoundland The Lamplighter Game on Paths with Complete Lamps [PDF]

Lamplighter graphs are a class of finite graphs exhibiting exotic geometries. We establish non-trivial upper and lower bounds on the cop number of lamplighter graphs by considering retracts of these graphs, and we provide a linear upper bound on the cop number of a certain subclass of lamplighter graphs by considering the Lamplighter Game played on paths of finite length.

ANTHONY BONATO, Toronto Metropolitan University What we know and what we don't know about cooling [PDF]

Cooling uses the same rules as burning, but instead of spreading efficiently, it spreads as inefficiently as possible. For some graphs, cooling is easier to analyze than burning and vice versa. We provide an overview of what is known and unknown in cooling, give results for graph families and bounds, and discuss new results on cooling graph products.

NANCY CLARKE, Acadia University Further results on the Cops and Insightful Robber model [PDF]

We consider a variation of the Cops and Robber game, introduced by Huggan and Nowakowski, in which the cops and the robber move simultaneously yet the robber is able to react to the cops' moves. As per usual with such models, our parameter of interest is the minimum number of cops that suffice to win on a given graph. We consider our parameter for planar and, in particular, bipartite planar graphs, and give bounds for strong and lexicographic products and some exact results. We also introduce a new parameter, the push number of a graph, and use it to compare this game with other variants. This is joint work with Danny Dyer and William Kellough.

ALEX CLOW, Simon Fraser University Can Cop Number Equal Independence Number? [PDF]

In 2022 Turcotte asked if $c(G) < \alpha(G)$ for all graphs with $\alpha(G) \geq 3$. Recently, Char, Maniya, and Pradhan proved this is false when $\alpha = 3$ by demonstrating a single graph with cop number and independence number $3$. The problem was not resolved for graphs with independence number greater than $3$. We settle this problem using random graphs by proving the stronger result that for all $k\geq 1$ there exists a graph $G$ such that $c(G) = \alpha(G) = \theta(G) = k$. Next, we consider the structure of graphs achieving $c(G) = \theta(G)$, and in doing so we prove that if $G$ is a perfect graph with $\alpha(G)\geq 4$ then $c(G) < \alpha(G)$.

\vspace{1cm} This is joint work with Imed Zaguia.

MELISSA HUGGAN, Vancouver Island University The Infectious Vaccination Problem, Part II [PDF]

This is a continuation of the talk by Margaret-Ellen Messinger about the model for the competing spread of a virus and self-disseminating vaccine. In this talk, we present some results about infinite $n$-dimensional Cartesian and strong grids, and examine a connection to the strength of $n$-dimensional hypercubes. This is joint work with J. Enright, E. Hunter-Frankland, M.E. Messinger, and D. Pearson.

MEAGAN MANN, Queen's University Predicting The Cop Number Using Machine Learning [PDF]

Cops and Robbers is a pursuit evasion game played on a graph, first introduced independently by Quilliot and Nowakowski and Winkler over four decades ago. A main interest in recent the literature is identifying the cop number of graph families. The cop number of a graph, $c(G)$, is defined as the minimum number of cops required to guarantee capture of the robber. Determining the cop number is computationally difficult and exact algorithms for this are typically restricted to small graph families. This paper investigates whether classical machine learning methods and graph neural networks can accurately predict a graph's cop number from its structural properties and identify which properties most strongly influence this prediction. Of the classical machine learning models, tree-based models achieve high accuracy in prediction despite class imbalance, whereas graph neural networks achieve comparable results without explicit feature engineering. The interpretability analysis shows that the most predictive features are related to node connectivity, clustering, clique structure, and width parameters, which aligns with known theoretical results. Our findings suggest that machine learning approaches can be used in complement with existing cop number algorithms by offering scalable approximations where computation is infeasible.

TRENT MARBACH, Acadia University Between Burning and Cooling: Liminal Burning on Graphs [PDF]

Liminal burning generalizes both the burning and cooling processes in graphs. In $k$-liminal burning, a Saboteur reveals $k$-sets of vertices in each round, with the goal of extending the length of the game, and the Arsonist must choose sources only within these sets, with the goal of ending the game as soon as possible. The result is a two-player game with the corresponding optimization parameter called the $k$-liminal burning number. For $k = |V(G)|$, liminal burning is identical to burning, and for $k = 1$, liminal burning is identical to cooling.

Using a variant of Sperner sets, $k$-liminal burning numbers of hypercubes are studied along with bounds and exact values for various values of $k$. In particular, we determine the exact cooling number of the $n$-dimensional hypercube to be $n.$ We analyze liminal burning for several graph families, such as Cartesian grids and products, paths, and graphs whose vertex sets can be decomposed into many components of small diameter.

JOHN MARCOUX, Toronto Metropolitan University Localization and the Ball Dimension [PDF]

In this talk we introduce a new variant of the metric dimension called the \emph{ball dimension} as a tool for studying a multi-robber variant of the Localization game as well as the original Localization game. This new variant weakens the resolving condition of the metric dimension and only requires vertices which share a neighbour to be resolved. We will first explore connections between the metric dimension, ball dimension, and the Localization game. We will then use the ball dimension as a tool to explore bounds on the localization number for highly symmetric graphs, namely hypercubes, Johnson graphs, and Grassmann graphs. We also demonstrate a surprising connection between the ball dimension, Johnson graphs, and projective planes. We conclude with some open problems.

This is joint work with Trent Marbach and Kerry Ojakian.

MARGARET-ELLEN MESSINGER, Mount Allison University The Infectious Vaccination Problem, Part 1 [PDF]

We consider a variant of $b$-FIREFIGHTER called the Infectious Vaccination Problem (INFECTVAX) in which the defence also spreads. An infection breaks out at time-step $0$ and during each time-step $t>0$, the vaccine spreads, new vertices are directly inoculated, and the contagion spreads. Thus, INFECTVAX is a deterministic discrete-time model for the competing spread of a virus and self-disseminating vaccines in a graph. In this preliminary talk, we introduce the model, present some hardness results, and make some observations about subgraphs. This is joint work with J. Enright, M.A. Huggan, E. Hunter-Frankland, and D. Pearson.

TEDDY MISHURA, Toronto Metropolitan University (TMU) Cooling Generalized Hypercubes [PDF]

Graph cooling was introduced as an analogue to the well known game of graph burning. Both of these games are round based processes where fires spread from burning vertices to adjacent vertices and the player (the Arsonist) lights a vertex on fire every round. In graph burning, the player must burn all the vertices of $G$ as quickly as possible, whereas in cooling, the player must burn all the vertices of $G$ as slowly as possible. The hypercube graph of dimension $n$, written $Q_n$, is the Cartesian product of $n$ copies of the graph $P_2.$ Its cooling number was recently shown to be exactly $n$. In this talk, I analyze the cooling number of two families of graphs that can be viewed as extensions of $Q_n$—Cartesian products of complete graphs $K_m$ and Cartesian products of path graphs $P_k$. I end the talk with a brief discussion of open problems.

Based on joint work with Anthony Bonato, MacKenzie Carr, Caleb Jones, and Trent Marbach.

JOY MORRIS, University of Lethbridge Eternal domination in Cayley graphs [PDF]

As usual, a dominating set in a graph is a set of $D$ vertices such that every vertex of the graph is either in $D$, or is adjacent to a vertex of $D$. We can turn the idea of domination into a defensive game or strategy by thinking of the dominating set as a collection of guards, and insisting that should any vertex outside of $D$ be attacked, the guards must be able to move along edges so that one of the guards moves to the attacked vertex, and the layout of the guards after the move is again a dominating set for the graph. If it is possible to continue to reconfigure the guards in this way forever, no matter what sequence of vertices is attacked, then we say that $D$ is an eternal dominating set for the graph.

A Cayley graph is a graph with a great deal of symmetry: its automorphism group acts transitively on the vertices of the graph; moreover there is a subgroup of the automorphism group that acts regularly (sharply transitively) on the vertices. In some situations, symmetry can provide interesting and effective strategies for graph searching problems, but the presence of game pieces such as searchers often essentially breaks the symmetry of the graph, rendering it much less useful.

In this talk I will present recent results about eternal dominating sets for Cayley graphs. This is based on joint work with MacKenzie Carr, Nancy Clarke, and Gary MacGillivray.

TODD MULLEN, University of Prince Edward Island Cops and Robbers and Barricades [PDF]

In a game of Cops and Robber, a barricade is an object that can be placed to occupy a vertex, preventing that vertex from being used in future turns. The concept of a barricade opens up a number of questions such as "Where are they placed?", "When are they placed?", "Who can place them?", and "Who can and cannot occupy those vertices on future turns?". We will discuss the classification of Cops and Robber variants and how barricades somewhat evade strict classification. Joint work with Dr. Erin Meger.

LOGAN PIPES, Memorial University of Newfoundland On The Radius of Location of Trees [PDF]

The metric dimension of a graph represents the minimum number of cell towers needed to be placed among the vertices of a graph such that the location of an unknown agent can be uniquely determined using only its distances to each of the cell towers. The radius of location of that graph then represents the minimum possible "strength" of the cell towers over all optimal layouts this number of towers. In particular, a cell tower cannot distinguish two locations if they are outside of the range of that tower. We discuss this parameter on several classes of graph, with emphasis on caterpillars and trees in general. This is joint work with Danny Dyer and Melissa Huggan.

AMANDA PORTER, University of Victoria Edge Cops and Robber on Triangle-Free Graphs [PDF]

We consider an edge variant of the classic game of Cops and Robber, introduced by Dudek, Gordinowicz, and Prałat, where players occupy edges rather than vertices. The parameter of interest in this setting is the edge cop number of a graph: the minimum number of cops required to guarantee capture of the robber. We study the edge cop number of triangle-free graphs via its relationship to the cop number of their associated line graphs. In particular, we show that the edge cop number is unbounded on the class of triangle-free graphs, and characterize the triangle-free graphs that are edge cop-win.

This is joint work with Melissa Huggan and Gary MacGillivray.

top of page