Title: Domination, isolation and the Art Gallery Theorem

Abstract: In 2017, Caro and Hansberg [6] introduced the isolation problem, which generalizes the domination problem. Given a graph \(G\) and a set \(\mathcal{F}\) of graphs, the \(\mathcal{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 \(\mathcal{F}\). When \(\mathcal{F}\) consists of a \(1\)-clique, the \(\mathcal{F}\)-isolation number is the domination number. In addition to establishing many results on \(\mathcal{F}\)-isolation numbers, Caro and Hansberg [6] posed several problems. Solutions [1,3] will be presented together with other results. Chvatal's Art Gallery Theorem (ALT) [7] inspired a wealth of domination results (many of which are referenced in [6,8]) for the case where \(G\) is a maximal outerplanar graph (mop). Recently, Kaemawichanurat and the speaker [6] 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.
References:

1. [1] P. Borg, Isolation of cycles, Graphs and Combinatorics 36 (2020), 631–637.
2. [2] P. Borg, Isolation of connected graphs, arXiv:2110.03773.
3. [3] P. Borg, K. Fenech and P. Kaemawichanurat, Isolation of k-cliques, Discrete Mathe- matics 343 (2020), paper 111879.
4. [4] P. Borg, K. Fenech and P. Kaemawichanurat, Isolation of k-cliques II, Discrete Math- ematics 345 (2022), paper 112641.
5. [5] P. Borg and P. Kaemawichanurat, Extensions of the Art Gallery Theorem, Annals of Combinatorics (2022), in press, https://doi.org/10.1007/s00026-022-00620-4.
6. [6] Y. Caro and A. Hansberg, Partial domination - the isolation number of a graph, Filo- Math 31:12 (2017), 3925–3944.
7. [7] V. Chvátal, A combinatorial theorem in plane geometry, Journal of Combinatorial Theory Series B 18 (1975), 39–41.
8. [8] M. Lemańska, R. Zuazua and P. Zylinski, Total dominating sets in maximal outerplanar graphs, Graphs and Combinatorics 33 (2017), 991–998.

Peter Borg is a Professor in the Department of Mathematics within the Faculty of Science at University of Malta. He obtained a B.Sc.(Hons.) in Mathematics, Statistics and Operations Research from University of Malta in 2002, a Certificate of Advanced Studies in Mathematics from University of Cambridge in 2003, and a Ph.D. in Mathematics from The Open University in 2007. He has been a full-time lecturer of mathematics at University of Malta since 2007. He is engaged in research in combinatorial mathematics, focusing on extremal set theory and extremal graph theory. His research originally concerned intersecting families and cross-intersecting families of sets, and many of his results were inspired by the Erdős-Ko-Rado Theorem and Chvátal’s Conjecture. Since a few years ago, he has also been treating problems in domination, independence and related areas of graph theory, establishing sharp bounds on graph parameters.