Réunion d'ete SMC 2018
Fredericton, 1 - 4 juin 2018
Recherche par graphes et jeux de poursuite-évasion sur les graphes
Org: Dr. Danielle Cox (Mt. St. Vincent University), Dr. Christopher Duffy (University of Saskatchewan) et Dr. Danny Dyer (Memorial University)
[PDF]
Org: Dr. Danielle Cox (Mt. St. Vincent University), Dr. Christopher Duffy (University of Saskatchewan) et Dr. Danny Dyer (Memorial University)
[PDF]
- ANTHONY BONATO, Ryerson university
Throttling graphs [PDF]
-
In the game of Cops and Robbers played on graphs, if we increase the number of cops, then the cop number will monotonically decrease. We may view this as a trade-off between the number of cops and the capture time. In graph throttling, we minimize the sum of the number of cops and their corresponding capture time. Throttling has connections to matrix theory and the zero forcing number of a graph. We give a survey of graph throttling and present new results on throttling chordal graphs, unicylic graphs, and graphs with large throttling number.
- DANIELLE COX, Mount Saint Vincent University
Limited Visibility Cops and Robbers [PDF]
-
Limited visibility Cops and Robbers is a variation of the traditional Cops and Robbers game where the Cops can only see distance $ \ell \geq 1$ from their current location, but the Robber still has perfect information. Results regarding monotonicity, retracts, trees and chordal graphs will be presented. This is joint work with N. Clarke, C. Duffy, D. Dyer, S. Fitzpatrick and M.E. Messinger.
- DANNY DYER, Memorial University of Newfoundland
Looking for structure in watchman's walks [PDF]
-
In this talk, we will examine the watchman's walk problem: to find a minimum length closed dominating walk in a graph $G$. We call this length $w(G)$. We will discuss what we can say about $w(G)$ in terms of the diameter, and then in terms of the number of edges $m$ and the number of vertices $n$. Particularly, we consider the ratios $w(G)/m$ and $w(G)/n$, and consider the range of values possible, and the graphs that achieve extremal values.
- STEPHEN FINBOW, St Francis Xavier University
Eternal domination on 3 by n grids [PDF]
-
In the eternal dominating set problem, guards form a dominating set on a graph and, at each step, a vertex is attacked. To defend against the attack, each guard either remains in place or moves to a neighboring vertex in order to form a new dominating set that contains the attacked vertex. The minimum number of guards required to successfully defend against any possible sequence of attacks is called the eternal domination number. We will present the exact values of eternal domination numbers for $3 \times n$ grid graphs.
- SHANNON FITZPATRICK, University of Prince Edward Island
Burning Circulant Graphs [PDF]
-
In 2016, Bonato, Janssen and Roshanbin introduced the problem of {\it graph burning} in order to model the spread of a contagion through a network. Given a finite connected graph, the process of burning a graph begins with all vertices being unburned. At time step 1, a single vertex is chosen to be burned. In each subsequent time step, two things occur: (1) the fire spreads to all neighbours of a previously burned vertex, and those vertices become burned, and (2) another vertex is selected to be burned. The objective is to burn all the vertices of the graph, and the {\it burning number} of a graph is the minimum number of time steps required to do so.
In this talk, I will present results regarding the burning numbers of circulant graphs. For degree 3 circulant graphs, as well as particular degree 4 circulant graphs, the burning numbers have been determined exactly. For others, results include upper and lower bounds on burning number, as well as asymptotic results.
This talk is based on joint work with Leif Wilm.
- JARED HOWELL, Memorial University - Grenfell Campus
Structure and Criticality of Watchman's Walks [PDF]
-
A watchman's walk in a simple graph $G$ is a minimum closed dominating walk, an optimal way to move through a graph continuously and see (but not necessarily visit) every vertex. We denote the length of a watchman's walk in $G$ by $w(G)$. In this talk, we will look at the structure of watchman's walks in particular classes of graphs. We will also look at edge-criticality as it pertains to the watchman's walk. We say a graph is 1-watchman-edge-critical if $w(G+e)<w(G)$, for any edge $e$ in the complement of $G$. Some initial results on this will be presented.
- GARY MACGILLIVRAY, University of Victoria
Cops and robber on oriented graphs, and generalizations [PDF]
-
We use the context of playing on oriented graphs as a vehicle to talk about how the various versions of the cops and robber game all admit the same “solution” in the sense of how to tell which player wins, how to determine each player’s optimal strategy, and how to figure out the length of the game assuming the cops win.
