Graph Searching Online Seminar 2021

Organizers:
Anthony Bonato: Ryerson University (abonato@ryerson.ca)
Danielle Cox: Mount Saint Vincent University (danielle.cox@msvu.ca)
Margaret-Ellen Messinger: Mount Allison University (mmessinger@mta.ca)

Our hope is that this on-line seminar can encourage interactions and collaborations. It is hosted by the AARMS collaborative group: Graph Searching in Atlantic Canada, and supported by AARMS.

Talks are 30 minutes with time for questions and discussion at the end and is hosted using Zoom.

To be added to our mailing list and to obtain the seminar Zoom link please contact one of the organizers.

Note: For security of the meeting, we please ask that you do not share the Zoom link publicly. Please feel free to share with colleagues and post-doctoral fellows.

Next Talk:

Friday, April 8, 1pm (AST)
Speaker: Dr. Ryan Cushnam (Ryerson University)

Title: On Meyniel Extremal Families of Graphs

Abstract: Meyniel's Conjecture states that there is a constant such that for any connected graph, the cop number is bounded above by this constant times the square root of the order. Although there are sublinear bounds on the cop number, in general there is a large gap between known bounds and Meyniel's Conjecture. Therefore, graph families that obtain this conjectured asymptotic upper bound, called Meyniel extremal families, can be of interest. In this talk, we provide new Meyniel extremal families and explore their properties. We provide new constructions with control over degree, chromatic number, and diameter. Employing methods from hypergraphs, we explore the degrees in families that are not Meyniel extremal and give the best-known upper bound on the cop number of vertex-transitive graphs with a prescribed degree. We also explore the connection between Meyniel extremal families and bipartite graphs. This is joint work with Anthony Bonato and Trent Marbach.

Past Talks:

Friday, January 14, 1pm (AST)
Speaker: Dr. Pawel Pralat (Ryerson University)
Title: Semi-random process

Abstract: The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible.

During the talk, we will focus on the following problems: a) perfect matchings, b) Hamilton cycles, c) constructing a subgraph isomorphic to an arbitrary fixed graph G. We will also consider a natural generalization of the process to s-uniform hypergraphs.

Friday, February 11, 1pm (AST)
Speaker: Dr. Mohamed Omar (Harvey Mudd College)
Title: Burning Graph Classes

Abstract: Recent attention has been given to the process of graph burning, a process that models the propagation of nefarious agents through networks. Particular attention has been given to determining worst case analysis of the graph burning process. The Graph Burning Conjecture proposes an upper bound on the time a burning process takes to complete on a graph, as a function of the vertices. This upper bound has been verified for many graph classes across many papers, however many of the methods are particular to the given classes at hand. In contrast, we present systematic methods that take in a graph class and output graphs in the class that satisfy the conjecture. This approach hones in on some of the remaining mystery of the Graph Burning Conjecture, especially as it relates to graphs with prescribed degree conditions. This is joint work with Vibha Rohilla.
Slides.

Friday, March 11, 1pm (AST)
Speaker: Dr .Petra Wolf (University of Trier)
Title: The Game of Cops and Robbers on Edge Periodic Temporal Graphs

Abstract: We consider the cops and robbers game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i.e., for each edge e, a binary string s_e determines in which time step the edge is present, namely the edge e is present in time step t if and only if the string s_e contains a 1 at position t mod |s_e|. This periodicity allows for a compact representation of an infinite TVG. We prove that even for very simple underlying graphs, i.e., directed and undirected cycles, as well as graphs with constant sized vertex cover, the problem whether a cop-winning strategy exists is NP-hard and W[1]-hard parameterized by the number of vertices. Further, we present lower bounds matching upper bounds from the literature for the relation between the length of an underlying cycle and the least common multiple of the lengths of binary strings describing edge-periodicities over which the graph is robber-winning.
Video: https://youtu.be/b7Ly1kqUZBQ

Friday, November 19, 1pm (ADT)
Speaker: Dr. Karen Gunderson (University of Manitoba)
Title: Graph burning in a growing network
Abstract: Graph burning is a discrete-time process on graphs, where vertices are sequentially burned, and burned vertices cause their neighbours to burn over time, modelling social contagion in a network. While most of the work on this process has focussed on a fixed finite graph, in real-world applications, networks are often growing and changing over time. In this talk, I will consider extremal properties of graph burning in a sequence of growing grids in the Cartesian plane. In this setting, it no longer makes sense to think about number of steps required to burn all vertices, but rather to understand the possible `densities' of burning vertices over time.

In this talk, I will focus on sequences of growing grids in the Cartesian plane, centred at the origin. In some cases of slowly growing grids, all possible achievable densities of burning vertices can be determined. For faster growing grids, there is a threshold behaviour for the speeds of growth for which a positive density is possible. I will survey the problems, sketch some of the proofs and discuss some open problems. Based on joint work with Anthony Bonato and Amy Shaw.

Friday, December 10, 1pm (AST)
Speaker: Dr. Andrea Burgess (University of New Brunswick, Saint John)
Title: The deduction game

Abstract: In this talk, we introduce a new variant of cops and robbers called the deduction game. In this game, the cops attempt to capture an invisible robber in one move, but cops situated on different vertices cannot communicate with each other to coordinate strategy. For this reason, the cops must deduce how other cops will move and make their own moves accordingly. We describe the rules governing the cops' movements, and introduce the deduction number, that is, the minimum number of cops required to guarantee capture of the robber in the deduction game. We give various bounds on the deduction number, and consider the game in certain graph classes. This is joint work with Danny Dyer and Mozhgan Farahani.

Thank you to our sponsor