Pure Mathematics Colloquium

Dates

Tuesday, April 4, 2023 - 14:30 to 15:15

Speakers: Peter Borg /Julien Portier

Abstract: Domination, Isolation and the Art Gallery Theorem/On the total domination game and the ¾ conjecture

Abstract: Domination, Isolation and the Art Gallery Theorem (Peter Borg - (University of Malta) - 2.30pm)

In 2017, Caro and Hansberg introduced the isolation problem, which generalizes the domination problem. Given a graph G and a set F of graphs, the F-isolation number of G is the size of a smallest subset D of the vertex set of G such that G - N[D] (the graph obtained from G by removing the closed neighbourhood of D) does not contain a copy of a graph in F. When F consists of a 1-clique, the F-isolation number is the domination number. In addition to establishing many results on F-isolation numbers, Caro and Hansberg posed several problems. Solutions will be presented together with other results. Chvatal's Art Gallery Theorem (ALT) inspired a wealth of domination results for the case where G is a maximal outerplanar graph (mop). Recently, Kaemawichanurat and the speaker improved Chvatal's sharp upper bound n/3 on the domination number of an n-vertex mop G, and by treating {K_{1,k}}-isolation of G, they improved ALT for the case where at least one of every k+1 consecutive corners of an `art gallery' (a polygon in general) needs to be guarded.

Abstract: On the total domination game and the ¾ conjecture (Julien Portier  (Cambridge) - 3.15pm)

We will talk about the so-called total domination game and give a proof of the ¾ Conjecture for the total domination game, which gives a tight bound on the length of this game. We will also discuss other results and open problems about domination games.