Independent dominating sets in planar triangulations

Fábio Botler, Cristina G. Fernandes, Juan Gutiérrez

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…