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…

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…

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…

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…

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…

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…

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…

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…