Réunion d'hiver SMC 2022
Toronto, 2 - 5 décembre 2022
- ANDREA BURGESS, University of New Brunswick Saint John
The Deduction Game [PDF]
-
The deduction game is a variant of the game of cops and robbers in which cops must capture an invisible robber, but cannot communicate with cops on other vertices to co-ordinate strategy. Thus, cops must "deduce" how other cops will move and make their own moves accordingly. We discuss characterizations of the game and connections with zero-forcing. We give bounds on the number of cops required to capture the robber, and discuss the game in some classes of graphs. This talk includes joint work with Danny Dyer, Mozhgan Farahani, Krishna Narayanan, Kerry Ojakian, Mingyu Xiao and Boting Yang.
- JESSICA ENRIGHT, University of Glasgow
Multilayer cops-and-robbers [PDF]
-
(joint work with Will Pettersen, John Sylvester, and Kitty Meeks)
Multilayer graphs are graphs with multiple edge sets on a single vertex set. For example, consider a graph in which towns or neighbourhoods are vertices and different edge sets are different ways of getting between them: one edge set might be links by rail or underground, another geographic adjacency, and another fast road links. We have been studying the game of cops-and-robbers on multilayer graphs. Here, we allow each cop to move on only one layer but allow the robber to freely move on edges from any layer - from our previous analogy cops are restricted to just one mode of transport each, but robbers may use any combination. We have been interested in various problems, including a multilayer version of cop-number and optimal cop allocation between layers.
After giving several motivating examples that initially confounded our intuition, I will report on hardness results for determining multilayer cop number and performing cop allocation. I will also outline a positive relating the multilayer cop number and the treewidth of the graph on which the robber moves.
- CALEB JONES, Memorial University of Newfoundland
Burning Triple Systems [PDF]
-
We introduce a round-based model much like graph burning which applies to hypergraphs. The rules for this new model are very natural, and generalize the original model of graph burning. A second model called ``lazy burning'' is also introduced, along with a new parameter, the lazy burning number. We briefly discuss results and bounds for both models that apply to general hypergraphs, and then move on to the discussion of triple systems, which have a special significance in the context of burning. We focus mainly on Steiner triple systems, obtaining a lower bound on the burning number and an upper bound on the lazy burning number. Finally, we show some additional interesting results such as the fact that there are infinitely many Steiner triple systems with lazy burning number 3.
- TRENT MARBACH, Toronto Metropolitan University
Limited visibility localization [PDF]
-
A modification to the typical Cops and Robbers game limits the cops' knowledge by introducing a restriction known as \emph{$k$-visibility}. This restriction is that the cops only know the robber's location if some cop is distance at most $k$ from the robber.
Previous work has primarily focused on the case with $k=0$ and $k=1$, although recent work has explored the general case.
We introduce the \emph{$k$-visibility Localization game}, focusing on the case $k=1$.
Play in this variant naturally splits up into two phases.
For a graph $G$, we write
$\text{prox}_1(G)$
to indicate the minimum number of cops required to see the robber on $G$ and $\zeta_1(G)$ to indicate the minimum number of cops required to capture the robber on $G$.
The results that we present will show connections between these new graph parameters and the previously studied graph isoperimetric parameters, which are two parameters that bound a subgraph's boundary with respect to the number of vertices in the subgraph. In particular, we introduce a $h$-index for the graph isoperimetric parameter, which provides an alternate view of how `large' the graph isoperimetric parameter is for a given graph. We then show how previously published results on the graph isoperimetric problem can be utilized using the $h$-index idea to give lower bounds on $\zeta_1(G)$ and $\text{prox}_1(G)$ for several graph families.
- JOHN MARCOUX, Toronto Metropolitan University
Distance-Restricted Firefighting on Finite Graphs [PDF]
-
In the classic version of the game of firefighter, on the first turn a fire breaks out on a vertex in a graph $G$ and then $k$ firefighters protect $k$ vertices. On each subsequent turn, the fire spreads to the collective unburnt neighbourhood of all the burning vertices and the firefighters again protect $k$ vertices. Once a vertex has been burnt or protected it remains that way for the rest of the game. We previously introduced the concept of distance-restricted firefighting where the firefighter's movement is restricted so they can only move up to some fixed distance $d$ and they may or may not be permitted to move through burning vertices. In this talk we establish the NP-Completeness of the distance-restricted versions of the Maximum Vertices Saved problem as well as covering some interesting properties of the Expected Damage function. This is joint work with David Pike, Andrea Burgess, and Verafin Inc.~as part of the Mitacs Accelerate Program.
- MICHAEL MOLNAR, Toronto Metropolitan University
Limited Visibility Localization [PDF]
-
We explore a variation of the localization game, where a set of cops seek to identify the location of an invisible robber using distance probes. We define the parameter $\zeta_1(G)$ to be the minimum number of cops required to win the game on a graph $G$, with probes only revealing 0, 1, or other. We evaluate $\zeta_1(G)$ on various graph classes, and give upper bounds for trees via their order, height, and number of leaf vertices. We show that there are trees $T$ for which $\zeta_1(T)$ is unbounded. This is in stark contrast to the localization game, where $\zeta(T) \le 2$ for all trees.
- TODD MULLEN, University of Prince Edward Island
Surrounding an Active Robber [PDF]
-
The Surrounding Cop Number is a recently introduced parameter which
measures the number of Cops required not to capture the Robber, but rather to occupy all vertices adjacent to the Robber (whether or not a Cop is on the Robber’s vertex). In the Cops and Robber variant, Surrounding Cops and Robber, if a Cop ever lands on the Robber’s vertex, the Robber doesn’t lose, but rather he is simply compelled to move on his next turn to a vertex that doesn’t contain a Cop. In this talk, we introduce two similar variants to Surrounding Cops
and Robber, one with an active Robber and one with a cheating Robber, that attempt to address certain peculiarities in the Cops’ and Robber’s respective strategies in Surrounding Cops and Robber. We conclude by discussing an interesting family of graphs on which the Active Number and Cheating Number differ, and speculate the size of the largest possible difference between these two parameters on a given graph.
- JD NIR, Toronto Metropolitan University
On the Best Way to Play with Fire: an Adversarial Burning Game [PDF]
-
Graph burning is a discrete-time process that models the spread of influence in a network. Vertices are in one of two states: either burning or unburned. In each round, a burning vertex causes all of its neighbours to become burning and then a previously unburned vertex is chosen whose state is changed to burning. Previous work has focused on bounding the number of turns necessary to burn an $n$-vertex graph. We introduce a variation of the graph burning process that incorporates an adversarial game played on a nested, growing sequence of trees. Two players, Arsonist and Builder, play in turns: Builder adds unburned vertices to create a larger tree, then burning vertices spread fire to their neighbours, and finally Arsonist 'lights' a new fire on an unburned vertex. This process repeats forever. Arsonist is said to win if the limiting fraction of burned vertices tends to 1, while the Builder is said to win if this fraction is bounded away from 1. We consider how the number of vertices granted to Builder each turn affects the optimal strategies for each player.
- BRITTANY PITTMAN, Toronto Metropolitan University
The localization game on directed graphs [PDF]
-
In the localization game played on graphs, a set of cops uses distance probes to identify the location of an invisible robber. This talk introduces an extension of this game and its main parameter, the localization number, to directed graphs. We present several bounds on the localization number of a directed graphs, including a tight bound via strong components, a bound using a linear programming problem on hypergraphs, and bounds in terms of pathwidth and DAG-width. We also consider the localization number of random and quasi-random tournaments. This is joint work with Anthony Bonato, Ryan Cushman, and Trent Marbach.