|
|||||
Movement and symmetry in graphs - Part I
Org: Karen Gunderson (University of Manitoba), Karen Meagher (University of Regina) et Joy Morris (University of Lethbridge)
[PDF]
Org: Karen Gunderson (University of Manitoba), Karen Meagher (University of Regina) et Joy Morris (University of Lethbridge)
[PDF]
- KAREN GUNDERSON, University of Manitoba
Bootstrap percolation on infinite graphs [PDF]
-
In $r$-neighbour bootstrap percolation, vertices of a graph are either `healthy' or `infected' and infection spreads to a healthy vertex with at least $r$ infected neighbours. Percolation is said to occur if all vertices are eventually infected. When vertices are infected initially at random, the main question is the value of the critical probability -- where percolation becomes more likely than not. I will present results on how the variance of vertex degrees affects the value of the critical probability in Galton--Watson trees and discuss some open problems on the critical probabilities for infinite regular graphs including Cayley graphs.
- JEANNETTE JANSSEN, Dalhousie University
An approximation algorithm for finding the zero-forcing number of a graph [PDF]
-
Consider the following graph process: Given a graph with vertices coloured black or white. At each step, if a black vertex has exactly one white neighbour, then this neighbour turns black. If the process turns all vertices black, then the initial set of black vertices is a zero-forcing set. The minimum size of a zero-forcing set in a graph $G$ is called the zero-forcing number $z(G)$. We give an approximation algorithm that finds a zero-forcing set of size at most $(pw+1)z(G)$, where $pw$ is the path-width of $G$.
This is joint work with Ben Cameron, Rogers Mathew, and Zhiyuan Zhang.
- KAREN MEAGHER, University of Regina
Open problems related to Erd\H{o}s-Ko-Rado type results [PDF]
-
I have been working on Erd\H{o}s-Ko-Rado type results using methods from Algebraic Graph Theory for many years. In this talk I will describe several problems and conjectures related to this work where my standard methods fail and I need new tools! These are all problems I am hoping to make progress on with the collaborative research group Movement and Symmetry in Graphs.
- JOY MORRIS, University of Lethbridge
Regular Representations [PDF]
-
A regular representation is a combinatorial object whose automorphism group is acting regularly (generally on the points). A regular action is one that is sharply transitive: i.e., there is precisely one automorphism taking any point to any other. I will give an overview of some of the results on regular representations (graphical, digraphical, tournament, etc.), including asymptotic results and results about when they can be easily detected.