Independent Dominating Sets in Planar Triangulations

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.