Independent Dominating Sets in Planar Triangulations

Abstract

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 \(\varepsilon\) for which every near planar triangulation on \(n\) vertices contains an independent dominating set of size at most \(\varepsilon n\)? We prove that \(2/7 \leq \varepsilon \leq 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.