Réunion d'hiver SMC 2019

Toronto, 6 - 9 décembre 2019

Graph Searching
Org: Anthony Bonato (Ryerson University), Stephen Finbow (St. Francis Xavier University) et Erin Meger (Ryerson University)
[PDF]

JANE BREEN, Ontario Tech University Kemeny's constant and random walks on graphs [PDF]: Kemeny’s constant is an interesting and useful quantifier of how well-connected the states of a Markov chain are, and is calculated using the eigenvalues of the transition matrix. By considering the random walk on a simple, undirected graph, and the eigenvalues of the normalized Laplacian matrix of the graph, we can compute Kemeny’s constant and regard this value as a graph parameter with a concrete interpretation in terms of the expected length of a random trip in the graph. Kemeny's constant has also been used to inform strategies for stochastic surveillance in a graph. In this talk we give a survey of known results, consider extremal graphs where Kemeny’s constant is largest possible, and present new techniques in spectral graph theory which facilitate the computation of Kemeny’s constant for these graphs.
NANCY CLARKE, Acadia University Cops and Robber with Decoys [PDF]: We consider a variation of the Cops and Robber game in which the robber side consists of a robber and a decoy which are indistinguishable to the cops except under certain conditions. The cops win when one of them moves onto the same vertex as the actual robber (i.e.~not the decoy) after a finite number of moves. The robber can throw the decoy to a neighbouring vertex on any move beyond his first. The decoy disappears after the cops' next move so there is only a single decoy in play at any time. We characterize decoy-copwin graphs in the case where the cop can distinguish between the robber and decoy only when he is on the same vertex as one of them. We also characterize such graphs if the cop can distinguish between the robber and decoy only when he has cornered at least one of them. This is joint work with D. DesRoches, M. Islam, and J. Diamond.
MELISSA HUGGAN, Ryerson University Cops and Eternal Robbers [PDF]: We consider a Cops and Robbers variant where the robber has allies! For a positive integer, t, the cops must capture the robber in at most t turns. When a robber is caught, a new robber appears elsewhere in the graph and the timer resets, giving the cops at most t turns to capture the new robber (from the current cop position). This process repeats. This can be viewed as an infinite number of plays of Cops and Robbers with the cop placement dependent on the previous capture position and each play has a fixed amount of time in which the cops must capture the robber. This talk introduces this variant of Cops and Robbers and presents early results. A main question to consider is the following: What is the minimum number of cops required to guarantee capture of the eternal robbers in at most t turns for each play?
This is joint work with Anthony Bonato, Trent Marbach, and Fionn Mc Inerney.
MARGARET-ELLEN MESSINGER, Mount Allison University Dominating vertex covers: a searchlight problem [PDF]: Abstract: Searchlight problems, inspired by the famous art gallery problem, attempt to use searchlights to find an intruder in a graph or polygon. We study a variation on the searchlight problem and consider the vertex-edge domination number of a graph. Our main result is to show the vertex-edge domination number of a cubic graph of order n is at most 9n/26. This is joint work with W.F. Klostermeyer and A. Yeo.
DANIEL MOGHBEL, Ryerson University Improved Bounds for Burning Fence Graphs [PDF]: Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a network. The burning process occurs over discrete time-steps, or rounds. In each round, a fire breaks out at a vertex, thus burning that vertex. Fires spread from burning vertices to their neighbors in successive rounds. The burning number of a graph $G$ is the minimum number of rounds necessary for every vertex of $G$ to burn. We consider the burning number of the $m \times n$ Cartesian grid graph, $G_{m,n}$. For $m = \omega(\sqrt{n})$, the asymptotic value of the burning number of $G_{m,n}$ was determined, but for $m = O(\sqrt{n})$, only the growth rate of that burning number was investigated. As such, we give new explicit bounds on the burning number of $G_{c\sqrt{n},n}$, where $c > 0$; a graph which we refer to as a fence graph. This is joint work with Anthony Bonato, Sean English, and Bill Kay.
BOJAN MOHAR, Simon Fraser University Cops and robbers in graphs of bounded degree [PDF]: We prove that one can effectively reduce the maximum degree of a graph so that the cop number of the resulting graph does not go down. As a consequence we show that, for every $\varepsilon > 0$ and every $n_0$, there exists a connected cubic graph of order $n\ge n_0$, whose cop number is at least $n^{1/2-\varepsilon}$.
This is joint work with Sebasti\'an Gonz\'alez Hermosillo de la Maza and Seyyed Aliasghar Hosseini.
RICHARD NOWAKOWSKI, Dalhousie University The value of catching a falling robber [PDF]: Cops-and-Robbers is a combinatorial but loopy game. Since `time to capture' is not an issue for the game values these tend not to be of use. If the robbers and cops are going in opposite directions the loopiness is eliminated. I'll consider one such situation, `Falling Robbers' introduced by Hill and followed up by Kinnersley, Pralat and West.

haut de la page