Events Search and Views Navigation
March 2023
Atlantic Graph Theory Seminar: Caleb Jones and Rylo Ashmore (Memorial University)
Speaker 1: Caleb Jones, Memorial University Title: Extending Graph Burning to Hypergraphs Abstract: We introduce a round-based model much like graph burning which applies to hypergraphs. The rules for this new model are very natural,and generalize the original model of graph burning. We also introduce a variant called lazy hypergraph burning, along with a new parameter, the lazy burning number. Interestingly, lazily burning a graph is trivial, while lazily burning a hypergraph can be quite complicated. Moreover, the lazy burning model is…
Find out more »Atlantic Graph Theory Seminar: Mohammad Salavatipour, U. Alberta
Approximation Schemes for Resource Minimization for Fire Containment Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not…
Find out more »Atlantic Graph Theory Seminar: Calum MacRury, University of Toronto
Approximation Schemes for Resource Minimization for Fire Containment The semi-random graph process is an example of an adaptive process for constructing a graph in which random edges are added step by step. It is adaptive in that there is an online algorithm which has partial control over which random edges are added. Through intelligent decision-making, the objective of the algorithm is to force the graph to satisfy a fixed graph property with high probability in as few rounds as possible. We first…
Find out more »September 2023
Atlantic Graph Theory Seminar
Time: 3.30pm, Atlantic time, Wednesday Sept.20 Speaker: Jessica McDonald, Auburn University Title: On flows (and group-connectivity) in signed graphs Abstract: In this talk we'll start by discussing flows in signed graphs and how it generalizes the usual notion of integer flows in graphs. In particular, flow-colouring duality of graphs in the plane can be re-interpreted using signed graphs in the projective plane. Also, where a flow in a graph can be viewed as a sum of flows on cycles, in…
Find out more »October 2023
Atlantic Graph Theory Seminar
Speaker: Iain Beaton, Acadia University Title: On the Unimodality of Nearly-Well Dominated Trees Abstract: A polynomial is said to be unimodal if its coefficients are non-decreasing and then non-increasing. The domination polynomial of a graph G is the generating function of the number of dominating sets of each cardinality in G, and its coefficients have been conjectured to be unimodal. In this talk we will show the domination polynomial of a tree T is unimodal so long as the sizes of the minimal…
Find out more »Atlantic Graph Theory Seminar
Two short talks by grad students Alex Clow and William Kellough. 'Live' viewing in Chase 227 for those at Dalhousie. Talk 1: Alex Clow, Simon Fraser University Polynomially Bounding the Oriented Chromatic Number in Euler Genus In this talk we consider the oriented chromatic number of graphs with bounded Euler genus. In particular, we present our proofs that the oriented chromatic number is at most $g^{6400}$ for sufficiently large $g$ and at least $\Omega((\frac{g^2}{\log g})^{1/3})$. This is a major improvement…
Find out more »November 2023
Atlantic Graph Theory Seminar
Detecting (Di)Graphical Regular Representations Speaker: Joy Morris, U. Lethbridge Abstract: Graphical and Digraphical Regular Representations (GRRs and DRRs) are a concrete way to visualise the regular action of a group, using (di)graphs. More precisely, a GRR or DRR on the group $G$ is a (di)graph whose automorphism group is isomorphic to the regular action of $G$ on itself by right-multiplication. For a (di)graph to be a DRR or GRR on $G$, it must be a Cayley (di)graph on $G$. Whenever…
Find out more »Atlantic Graph Theory Seminar
Speaker: Santiago Guzman-Pro, TU Dresden Title: Forbidden Tournaments and the Orientation (Completion) Problem Abstract: For a fixed finite set of oriented graphs F, the F-free orientation problem asks whether a given finite undirected graph G has an F-free orientation, i.e., whether the edges of G can be oriented so that the resulting oriented graph does not contain any oriented graph from F as an oriented (induced) subgraph. It was first noted by Bang-Jensen, Huang, and Prisner that when F…
Find out more »Atlantic Graph Theory Seminar
Speaker: Jordan Barrett, Toronto Metropolitan University Title: Graph burning, the burning number conjecture, and burning density Abstract: Graph burning is a discrete time process on a graph that acts as a simple model for the spread of social contagion in a network. Graph burning was introduced by Bonato, Janssen and Roshanbin in 2014, and with this introduction came the now famous "burning number conjecture". In the first half of my talk, I will introduce graph burning and give a brief overview of…
Find out more »January 2024
Atlantic Graph Theory Seminar
Speaker: Leslie Hogben, Iowa State University Title: Forts, (fractional) zero forcing, and Cartesian products of graphs Abstract: Zero forcing is an iterative process that repeatedly applies a rule to change the color of vertices of a graph $G$ from white to blue. The zero forcing number is the minimum number of initially blue vertices that are needed to color all vertices blue through this process. Standard zero forcing was introduced about fifteen years ago in the control of…
Find out more »