2022 CMS Summer Meeting
St. John's, June 3 - 6, 2022
Graph Searching
Org: Danny Dyer (Memorial University), Stephen Finbow (St. Francis Xavier University) and Brittany Pittman (Ryerson)
[PDF]
Org: Danny Dyer (Memorial University), Stephen Finbow (St. Francis Xavier University) and Brittany Pittman (Ryerson)
[PDF]
- RYLO ASHMORE, Memorial University
On Cuts and Cats [PDF]
-
The game of herding cats is a game on graphs where one player (the herder, omnipresent) is seeking to isolate the other (the cat, on a vertex). In each round, the herder permanently cuts one edge from anywhere in the graph, then the cat moves along any non-trivial path to a vertex. The game ends when the cat can no longer move. The score of the game is given by the total number of edges cut to isolate the cat. The cat's objective is to maximize the score (moving as many times as possible), while the herder's objective is to minimize the score (isolating the cat quickly).
We will look at how this game captures a potential end-game of a different game, as well as see some elementary results found so far. We find that this game is monotonic for subgraphs, view a structural property describing how centrality is good for the cat, and look briefly at the case of the infinite graph variant of this game.
- MOZHGAN FARAHANI, Memorial University of Newfoundland
The deduction model for cops and robber [PDF]
-
A variation of the game of cops and robber on graphs is studied in which the cops must capture an invisible robber in one move. Cops know each others' initial locations, but they can only communicate if they are on the same vertex. Thus, the challenge for the cops is to deduce the other cops' movement and move accordingly in order to capture the robber. This game is called the deduction model for cops and robber. In this thesis, the deduction number is introduced as the minimum number of cops needed to capture the robber in this model. For some classes of graphs, the deduction number is determined. We study the deduction number of trees and provide an upper bound for the Cartesian product of graphs. In particular, we give the deduction number for the hypercubes.
- JARED HOWELL, Memorial University, Grenfell Campus
The watchman's walk problem on graph products [PDF]
-
A watchman's walk in a graph $G$ is a minimum closed dominating walk. The watchman number of a graph $G$ is the length of a watchman's walk and is denoted by $w(G)$. First we introduce several lower bounds on $w(G)$ and apply them to determine $w(G)$ in some graph products. Pittman extended the definition of a watchman's walk to directed graphs in her M.Sc. thesis. In a natural way, both the walk and the domination in a digraph occurs in the direction of the arcs. We will finish this talk with some current work on the watchman's walk involving products of digraphs. This is joint work with Danny Dyer and Brittany Pittman.
- CALEB JONES, Memorial University of Newfoundland
Extending Graph Burning to Hypergraphs [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. In particular, we obtain bounds on the burning number of a hypergraph. We show that arbitrary hypergraphs do not satisfy a bound analogous to the burning number conjecture, and we therefore investigate certain families of hypergraphs such as Steiner triple systems. The lazy burning model on hypergraphs is introduced, along with a new parameter, the lazy burning number. Interestingly, lazily burning a graph is trivial, while lazily burning a hypergraph can be quite complicated. Moreover, the lazy burning model is a useful tool for analyzing the round-based model on hypergraphs.
- JOHN MARCOUX, Memorial University of Newfoundland
Firefighting with a Distance-Based Restriction [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. A common objective with respect to some infinite graph $G$ is to determine how many firefighters are necessary to stop the fire from spreading after a finite number of turns, commonly referred to as containing the fire. We introduce the concept of distance-restricted firefighting where the firefighters' movement is restricted so they can only move up to some fixed distance $d$ per turn rather than being able to move without restriction. We establish some general properties of this new game in contrast to properties of the original game, and we investigate specific cases of the distance-restricted game on the infinite square, strong, and hexagonal grids.
- REBECCA MILLEY, Grenfell Campus, Memorial University of NL
Average Unmonitored Time in the Watchman's Walk Problem [PDF]
-
The Watchman's Walk Problem is to find an optimal collection of walks (i.e. a "strategy") for one or more guards in a graph, so that each vertex is "monitored" (either on a walk or adjacent to a vertex on a walk), with the general goal of minimizing the length of time vertices are unmonitored. The vertices are monitored and unmonitored for various intervals during the strategy's period (LCM of all walk lengths). Each vertex has a longest unmonitored interval; ranging over all vertices, we can find the maximum unmonitored interval length for the graph. Most previous research has defined an optimal strategy as one which minimizes this maximum. This talk (joint work with Fatemeh Ghorbanivashki and Danny Dyer) introduces an alternative optimization: minimizing the *average* of the longest unmonitored intervals across all vertices. We investigate this average for various types of strategies (shared, disjoint, mixed) on paths and other simple trees.
- TODD MULLEN, St. Francis Xavier University
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, Active Robber and Fleeing 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 Fleeing Number differ, and speculate the size of the largest possible difference between these two parameters on a given graph.
- KERRY OJAKIAN, Bronx Community (C.U.N.Y.)
Tale of two games: Pyro versus Chop and Save [PDF]
-
Messinger and Yarnell recently introduced the Pyro game, a version of Firefighting in which the fire intelligently spreads to one vertex of its choice on each round of play. As usual, the Firefighter can protect one vertex on each round. A basic question when played on an infinite grid is this: Can the Firefighter contain the fire to a finite portion of the grid? Messinger and Yarnell show the answer is yes, and in fact show that the Firefighter can contain the fire to within distance 48 of its starting point. They conjecture that the Firefighter can keep the fire within distance 7 of its starting point. In this talk, I will reduce the Pyro game to a new game dubbed Chop and Save. Tools are developed for this new Chop and Save game, with the hope of using them to resolve the conjecture. This is very much work in progress!
- BRITTANY PITTMAN, Ryerson University
The localization capture time of a graph [PDF]
-
The localization game is a graph searching game analogous to Cops and Robbers, but where the robber is invisible, and the cops send distance probes in an attempt to identify the location of the robber. We present a graph parameter called the capture time, which measures the number of rounds in an instance of the localization game assuming optimal play. We consider graphs for which the capture time is linear in the order of the graph, and show that this holds for trees and interval graphs. We study monotonicity properties of capture time, and give bounds for the parameter on trees and multipartite graphs. New bounds on the localization number and capture time are given using treewidth and the chromatic number. We finish with an investigation of capture time on the incidence graphs on designs, and bounds are given in the case of projective planes.
- PAWEL PRALAT, Toronto Metropolitan University
Edge and Pair Queries---Random Graphs and Complexity [PDF]
-
Consider a query game played on a graph whose goal is to locate a vertex $v^*$ that is unknown to an adaptive query algorithm. Each query points to a pair of vertices $u$ and $v$, and the reply provides an answer that indicates which of those vertices is closer to $v^*$, breaking ties arbitrarily. The aim is to construct an algorithm performing as few queries as possible in the worst case. In this work we consider two types of queries: edge queries in which $u$ and $v$ need to be adjacent and pair queries in which there is no restriction on the choice of $u$ and $v$. The latter have not been considered in the literature before while the former have been extensively studied but only for trees. In this talk, we concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.
- BOTING YANG, University of Regina
On One-Visibility Cop-Win Strategies for Trees [PDF]
-
In this talk, we consider the one-visibility cops and robbers game. We discuss cop-win strategies for searching trees. We also present an algorithm for computing the one-visibility cop-win strategies of trees.