Seminar 2020

2020 Talks

• July 31
  Speaker: Dr. Trent Marbach (Ryerson University)
  Title: The Localization Number of Designs

Abstract: Meyniel's conjecture is a deep conjecture in the study of the game of cops and robbers. The conjecture posits that the cop number of graphs is at most asymptotic to the square root of the number of vertices. The incidence graphs of designs are examples of graphs that meet this conjectured upper bound, and so are of interest in the study of the game of cops and robbers along with other similar games.

In this talk, we will examine the localization game played on graphs, in which the cops localize a moving invisible robber using distance probes over several rounds. The localization number is the minimum number of cops needed to ensure the robber's capture. We present recent work on finding the localization number of incidence graphs of a number of designs

• July 10
  Speaker: Dr. Nicolas Nisse (Inria Sophia Antipolis)
  Title: Localization games in graphs.

Abstract: Given a graph, we want to localize a walking or immobile target by checking his (exact or relative) distance to as few vertices as possible. Precisely, each turn, one player can probe k vertices and receives the distances (or relative distances depending on the variant) from the target to these vertices. The main question is to establish a tradeoff between k and the number of turns to locate the target (the target may move or not depending on the variant). This problem can be considered as a game theoretic variant of the metric dimension of a graph. In this talk, we attempt to survey the different variants of this game, the results that have been obtained (complexity, bounds in various graph classes…) and the numerous open questions.

• June 26
  Speaker: Dr. Daniela Ferrero (Texas State University)
  Title: An Update on the Power Domination Problem
  
  Abstract: Power domination is a particular form of graph searching, introduced to study the monitoring process of electrical power networks. Electric power networks need continuous monitoring in order to prevent blackouts and power surges. In this talk, we introduce the power domination problem and show connections between power domination and other forms of graph searching, in graphs and digraphs. As electrical power systems are becoming increasingly more complex, so does their monitoring process, resulting in new questions about the power domination problem in graphs. We conclude the talk with some of these current challenges.
  recording below)
  

• June 12:
  Speaker: Dr. Alan Frieze (Carnegie Mellon University)
  Title: Two search problems in random graphs

Abstract:

Localisation game: We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The cop can take a number of rounds in order to locate the robber. The minimum number of probes per round, denoted $\zeta(G)$ for a given graph $G$, is called the localization number. We prove high probability upper and lower bounds for this quantity. Joint with Andrzej Dudek, Sean English, Calum MacRury, Pawel Pralat, Wesley Pegden.

Looking for vertex number one: Given an instance of the preferential attachment graph $G_n=([n],E_n)$, we would like to find vertex 1, using only `local' information about the graph; that is, by exploring the neighborhoods of small sets of vertices. We give a local algorithm to find vertex 1, which w.h.p. runs in time $O(\omega\log n)$ and which is local in the strongest sense of operating only on neighborhoods of single vertices. Here $\omega=\omega(n)$ is any function that goes to infinity with $n$. Joint with Wesley Pegden.
(recording below)

• May 29:
  Speaker: Dr. Nancy Clarke (Acadia University, Canada)
  Title: Cops and Robber with Misdirection

Abstract: We consider a variation of the Cops and Robber game in which the robber's side consists of a robber and a decoy that 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 turns. The robber can throw the decoy to a neighbouring vertex on any turn beyond his first; such a turn for the robber consists of first throwing the decoy and then moving. The decoy disappears after the cops' next turn 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, J. Diamond, and M. Islam.
(recording unavailable)

• May 15:
  Speaker: Dr. Florian Lehner (Graz University of Technology, Austria)
  Title: On the cop-number of toroidal graphs

Abstract: We study the cops-and-robber game introduced by Aigner and Fromme: $k$ cops are trying to catch a robber, on each turn the cops or the robber can move to adjacent vertices, and every player has perfect information.
A central question related to this game is, whether for a given graph $G$ there is a winning strategy using $k$ cops. The smallest $k$ for which this is the case is called the cop-number of $G$. In 1986, Andreae showed that for any fixed graph $H$, there is a constant upper bound (depending only on $H$) for the cop-number of graphs with no $H$-minor and asked for the best possible bound for the cop-number of toroidal graphs.
We show that the cop-number of toroidal graphs is at most $3$, thus answering Andreae's question and verifying a conjecture by Schroeder from 2001.
(recording below)

• May 1:
  Speaker: Dr. Bojan Mohar (Simon Fraser University)
  Title: Cops and robbers in graphs of large girth

Abstract: We establish a lower bound for the cop number of graphs of high girth in terms of the minimum degree, and more generally, in terms of a certain growth condition. We show, in particular, that the cop number of any graph with girth $g$ and minimum degree $d$ is at least $\tfrac{1}{g}(d - 1)^{\lfloor \frac{g-1}{4}\rfloor}$. This improves an old result of Frankl (1985) and seems to be "best possible".
(recording below)

• April 19:
  Speaker: Dr. Danny Dyer (Memorial University of Newfoundland)
  Title: Watchman decomposable graphs
  Abstract: A watchman’s walk in a graph G is a minimum-length closed dominating walk. While similar to dominating cycles, watchman’s walks exist in all connected graphs. However, they remain difficult to find and characterize. We consider a further problem with a combinatorial design flavour: given a graph G, can the graph be decomposed into watchman’s walks? That is, can G be partitioned into edge disjoint subgraphs, each of which is a watchman’s walk for G? Joint work with Jared Howell, Grenfell Campus, MUN.
  (recording unavailable)

Thank you to our sponsor