2023/10/17 by Aleksander B. G. Christiansen, Christiansen, Aleksander B. G., Eva Rotenberg +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.11254
openalex publication_date 2023/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 improves significantly on the previous best bound of 17n/53≈ n/3.117 by Špacapan [Š'20]. 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 [MT'96] 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.