Dominating Plane Triangulations

Michael D. Plummer, Dong Ye, Xiaoya Zha

In 1996, Tarjan and Matheson proved that if $G$ is a plane triangulated disc with $n$ vertices, $\gamma (G)\le n/3$, where $\gamma (G)$ denotes the domination number of $G$. Furthermore, they…