Triangulations Admit Dominating Sets of Size 2n/7.

We show that every planar triangulation on n > 10 vertices has a dominating set of size 2n/7 = n/3.5. This approaches the n/4 bound conjectured by Matheson and Tarjan [12], and improves significantly on the previous best bound of 17n/53 ≈ n/3.117 by Spacapan [18].

From our proof it follows that every 3-connected n-vertex near-triangulation (except for 3 sporadic examples) has a dominating set of size n/3.5. On the other hand, for 3-connected near-triangulations, we show a lower bound of 3(n — 1)/11 ≈ n/3.666, demonstrating that the conjecture by Matheson and Tarjan [12] cannot be strengthened to 3-connected near-triangulations.

Our proof uses a penalty function that, aside from the number of vertices, penalises vertices of degree 2 and specific constellations of neighbours of degree 3 along the boundary of the outer face. To facilitate induction, we not only consider near-triangulations, but a wider class of graphs (skeletal triangulations), allowing us to delete vertices more freely.

Our main technical contribution is a set of attachments, that are small graphs we inductively attach to our graph, in order both to remember whether existing vertices are already dominated, and that serve as a tool in a divide and conquer approach. Along with a well-chosen potential function, we thus both remove and add vertices during the induction proof.
We complement our proof with a constructive algorithm that returns a dominating set of size < 2n/7. Our algorithm has a quadratic running time.