## Abstract

We show that every planar triangulation on

*n*> 10 vertices has a dominating set of size 2*n*/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 17*n*/53 ≈*n*/3.117 by Špacapan [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 ≤ 2*n*/7. Our algorithm has a quadratic running time.Original language | English |
---|---|

Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Publisher | Society for Industrial and Applied Mathematics |

Publication date | 2024 |

Pages | 1194-1240 |

ISBN (Electronic) | 978-1-61197-791-2 |

DOIs | |

Publication status | Published - 2024 |

Event | 2024 Annual ACM-SIAM Symposium on Discrete Algorithms - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |

### Conference

Conference | 2024 Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Alexandria |

Period | 07/01/2024 → 10/01/2024 |

## Fingerprint

Dive into the research topics of 'Triangulations Admit Dominating Sets of Size 2*n*/7'. Together they form a unique fingerprint.