Triangulations Admit Dominating Sets of Size $2n/7$

Aleksander B. G. Christiansen, Eva Rotenberg, Daniel Rutschmann

We show that every planar triangulation on $n>10$ vertices has a dominating set of size $n/7=n/3.5$. This approaches the $n/4$ bound conjectured by Matheson and Tarjan [MT'96], and…