Independent Dominating Sets in Planar Triangulations

Botler F.; Fernandes C.G.; Gutiérrez J. · Electronic Journal of Combinatorics (2024) · DOI: 10.37236/12548

Resumen

In 1996, Matheson and Tarjan proved that every near planar triangulation on n vertices contains a dominating set of size at most n/3, and conjectured that this upper bound can be reduced to n/4 for planar triangulations when n is sufficiently large. In this paper, we consider the analogous problem for independent dominating sets: What is the minimum ε for which every near planar triangulation on n vertices contains an independent dominating set of size at most εn? We prove that 2/7 ≤ ε ≤ 5/12. Moreover, this upper bound can be improved to 3/8 for planar triangulations, and to 1/3 for planar triangulations with minimum degree 5. © The authors.

Instituciones: Universidad de Ingeniería y Tecnología