Réunion d'hiver SMC 2020

Ottawa, 7 - 11 juin 2021

Parcours de graphes
Org: Nancy Clarke (Acadia University), Margaret-Ellen Messinger (Mount Allison University) et Bojan Mohar (Simon Fraser University)
[PDF]

ANTHONY BONATO, X University New and improved bounds on the burning number of a graph [PDF]: The burning number conjecture states that the burning number of a connected graph is at most $\lceil \sqrt{n} \rceil.$ Using an algorithmic approach, we provide the best known upper bound for the burning number of a connected graph: $$\bigg \lceil \frac{\sqrt{12n+64}+8}{3} \bigg \rceil = \sqrt{(4/3)n} +O(1) .$$
NANCY CLARKE, Acadia University On the Hyperopic Cops and Robber Game [PDF]: We consider the hyperopic version of the Cops and Robber game, a variation in which the robber is invisible to the cop side unless outside the neighbourhood of a cop. The hyperopic copnumber is analogous to the copnumber. We present a variety of results on this parameter for various classes of graphs, including Cartesian products and graphs of diameter 2.
This is joint work with S. Finbow, M.E. Messinger, and A. Porter.
STEPHEN FINBOW, St Francis Xavier Eternal Domination of Grid Graphs [PDF]: The eternal domination number, denoted $\gamma_{all}^\infty (G)$, of a graph $G$ is the number of guards required to respond the graph against an infinite sequence of attacks from an unconstrained intruder. On each turn the intruder picks a vertex to ``attack" and each guard is allowed to move to an adjacent vertex after the attack. To successfully defend the attack, a guard must finish the turn on the attacked vertex. We will look at the work that has been done to understand eternal domination on grid graphs and discuss some recent work and observations on $6 \times n$ grid graphs.
SEYYED ALIASGHAR HOSSEINI, Simon Fraser Univesity Meyniel’s conjecture on graphs of bounded degree [PDF]: The game of Cops and Robbers is a well known pursuit-evasion game played on graphs. It has been proved that cubic graphs can have arbitrarily large cop number $c(G)$, but the known constructions show only that the set $\{c(G) \mid G \text{ cubic}\}$ is unbounded. In this talk we prove that there are arbitrarily large subcubic graphs $G$ whose cop number is at least $n^{1/2-o(1)}$ where $n=|V(G)|$. We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weaker version of Meyniel's conjecture for all graphs.
MELISSA HUGGAN, Mount Allison University Efficiently locating an invisible adversary [PDF]: The localization game is a variant of Cops and Robbers, where the robber is invisible, and the cops send distance probes in an attempt to identify the location of the robber. In this talk, we will explore the localization capture time which measures the time it takes the cops to locate an invisible robber assuming optimal play. We conjecture that the localization capture time is linear in the order of the graph and show that the conjecture holds for several graph families.
This is joint work with Natalie C. Behague, Anthony Bonato, Trent G. Marbach, and Brittany Pittman.
VESNA IRŠIČ, Simon Fraser University Winning vs. catching in the game of Cops and Robber on manifolds [PDF]: In a recently introduced variant of the game Cops and Robber that is played on metric surfaces, cops win the game if they can get arbitrarily close to the robber. On the other hand, cops catch the robber if one of them occupies the same point as the robber. In this talk we will discuss an interesting phenomena that the difference between the number of cops needed to catch the robber and the number of cops needed to win the game can be arbitrarily large. For example, one cop can win the game on an $n$-dimensional ball, while $n$ cops are needed to catch the robber.
Joint work with Bojan Mohar and Alexandra Wesolek.
GARY MACGILLIVRAY, University of Victoria Eternal Roman Domination in Trees [PDF]: Imagine a collection of mobile guards located at the vertices of a graph $G$ such that there are 0, 1 or 2 guards located at each vertex. If every vertex with 0 guards is adjacent at a vertex with 2 guards, then the configuration of guards is called a Roman dominating configuration. We consider a discrete-time, dynamic process in which the goal is to maintain a Roman dominating configuration for all time. At each time step a vertex $v$ with 0 guards is specified and the guards must reconfigure so that 1 or 2 guards relocate to $v$ and the the resulting configuration of guards is a Roman dominating configuration. During the reconfiguration each guard either stays in place of moves along an edge to an adjacent vertex. We show that if $G$ is a tree with $n$ vertices, then it is always possible to eternally maintain a Roman dominating configuration with $\left\lceil\frac{7n}{8}\right\rceil$ guards, and describe all trees for which no smaller number of guards suffices.
ERIN MEGER, Concordia University Distanced Eternal Domination on Graphs [PDF]: Eternal domination in a graph is a dynamic process which protects a graph from an infinite sequence of vertex attacks. In eternal $k$-domination, a set of guards seeks to protect the graph using a distance $k$ dominating set. There is an attack that occurs and the guards move positions up to distance $k$, to cover the attacked vertex, subsequently another attack occurs and they must move from their present positions. The minimum size of a set such that the graph can be protected from attacks indefinitely is called the eternal $k$ domination number of the graph, denoted $\gamma_{all,k}^{\infty}(G)$. In this talk, we will focus on the case where $k=2$, and detail the result for the case of perfect $m$-ary trees of depth $d$. For such graphs $T$: $$\gamma_{all, 2}^{\infty}(T)=1+\frac{m^d-1}{m^2-1}$$ In general, the computation of this parameter is not known for most graphs, and determining if a set is an eternal $k$-dominating set is a difficult problem. Other results will be discussed, and open problems towards a reduction on trees will be presented.
BOJAN MOHAR, SFU Cops and Robbers on geodesic spaces [PDF]: The game of Cops and Robber is traditionally played on a finite graph. The purpose of this talk is to introduce and analyze the game that is played on an arbitrary geodesic space (a metric space in which each pair of points at distance d is connected by a geodesic of length d). The game is defined in such a way that it preserves the beauty and power of discrete games played on graphs and also keeps the specialties of the pursuit-evasion games played on polyhedral complexes. It is shown that the game can be approximated by finite games of discrete type. As a consequence a min-max theorem is obtained for the version of the game where the goal of the cops is to minimize the distance to the robber throughout the duration of the game.
BOTING YANG, University of Regina A Linear-Time Algorithm for the One-Visibility Cop Number of Trees [PDF]: In this talk, we consider the one-visibility cops and robbers game. We give strategies to search trees according to their structures. We present a linear-time algorithm for computing the one-visibility cop number of trees. We also give relations between one-visibility and zero-visibility cop numbers. This is joint work with Tanzina Akter.

haut de la page