Discrete-Time Processes on Graphs
Org:
Nancy E. Clarke (Acadia University),
Alexander Clow (Simon Fraser University) and
Erin Meger (Queens University)
[
PDF]
- CAELAN ATAMANCHUK, McGill University
- ANDREA BURGESS, University of New Brunswick
- MACKENZIE CARR, Toronto Metropolitan University
- NANCY CLARKE, Acadia University
- ALEXANDER CLOW, Simon Fraser University
The Hole Story for Cop Number [PDF]
-
The cop number of a graph,
written $c(G)$,
is a central invariant in the study of discrete-time processes on graphs.
One advantage of cop number is its deep and well documented connection
to concepts in structural graph theory, such as graph minors, subgraphs, and induced subgraphs.
This talk will survey recent work on
the connection between cop number and the structure of holes in a graph.
A hole is an induced cycle of length at least $4$.
In doing so
we will show that any graph $G$ with $c(G) = \theta(G)=k\geq 2$,
where $\theta(G)$ is the clique cover number,
has $C_\ell$ as an induced subgraph for all $3\leq \ell \leq k+1$.
We will also prove that in any graph without holes of length at most $t$,
$N[P]$ can be guarded by $1$ cop for any short (as a function of $t$) induced path $P$,
even when $P$ is not a shortest path.
- JULIEN CODSI, Princeton University
- WILLIAM KELLOUGH, Memorial University of Newfoundland
Optimal Graph Burning Sequences and the Vertices They Contain [PDF]
-
Graph burning is a process that models a social contagion spreading through a network. Many papers that study graph burning focus on how quickly the process can be completed on a given graph or a given family of graphs. In this talk, we instead focus on determining which vertices enable a social contagion to spread through a given graph in optimal time. We explore this idea for various families of graphs. We also demonstrate how to construct graphs that have relatively few vertices that the contagion can use to spread in optimal time. Joint work with Beth Ann Austin, Alfie Davies, Danny Dyer, and Logan Pipes.
- ERIN MEGER, Queen's University
- PAWEL PRALAT, Toronto Metropolitan University
- BEN SEAMONE, Universite de Montreal