Domination of triangulated discs and maximal outerplanar graphs

• Published in: Applied mathematics and computation 2024-07, Vol.473, p.128648, Article 128648
• Main Authors: Renders, Jarne, Tokunaga, Shin-ichi, Zamfirescu, Carol T.
• Format: Article
• Language: English
• Subjects: Domination number; Outerplanar graph; Triangulation
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2024.128648

Given an infinite family of graphs, its domination ratio is the smallest real k such that for every large enough graph in the family, the ratio between its domination number and order is at most k. We give bounds for the domination ratios of various families of triangulated discs, disproving two conjectures of Tokunaga. For instance, we show that the domination ratio of triangulated discs of minimum degree 3 is at least 3/10. We also give a natural extension of a theorem on the domination number of maximal outerplane graphs, proven by Campos and Wakabayashi, and independently Tokunaga. Motivated by the Matheson-Tarjan Conjecture, we present observations on dominating triangulations via Jackson-Yu decomposition trees as well as an approach on how to efficiently dominate, given a triangulation, many large subtriangulations thereof. Throughout the paper, results are accompanied by computational experiments. •We give bounds for the domination ratio of various families of triangulated discs.•We give a theorem on the domination number of tree-linked outerplanar graphs.•We give an approach on how to efficiently dominate, given a triangulation, many large subtriangulations thereof.