## Events Search and Views Navigation

## February 2023

### Atlantic Graph Theory Seminar: Jérémie Turcotte, Université de Montréal

Progress towards the Burning Number Conjecture The burning number b(G) of a graph G is the smallest integer k such that G can be covered by k balls of radii respectively 0,...,k-1, and was introduced independently by Brandenburg and Scott at Intel as a transmission problem on processors and Bonato, Janssen and Roshanbin as a model for the spread of information in social networks. The Burning Number Conjecture claims that b(G)<=\lceil\sqrt{n}\rceil, where n is the number of vertices of G. This bound is tight for paths. The previous best bound for this problem, by Bastide…

Find out more »## March 2023

### Atlantic Graph Theory Seminar: Isaac McMullin and Ian George, Dalhousie University

Speaker 1: Isaac McMullin Existence of Optimal Split Reliability Polynomials One of the most common models of robustness of a graph against random failures has all vertices operational, but the edges independently operational with probability p. On one hand, one can ask for the probability that all vertices can communicate (all-terminal reliability) while on the other hand, we can ask that two specific vertices (or terminals) can communicate with each other (two-terminal reliability). While both of these questions have been…

Find out more »### Atlantic Graph Theory Seminar: Lucas Mol, Thomson Rivers University

Avoiding additive powers in words A word is a sequence of symbols taken from some finite alphabet. A square is a word of the form xx, where x is a nonempty word. It is well-known that there are infinite words over an alphabet of size 3 that contain no squares. Suppose now that the alphabet is some finite subset of the integers. An additive square is a word of the form xx', where x and x' have the same nonzero…

Find out more »### 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 »