Triangulations Admit Dominating Sets of Size 2n/7

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

5 Downloads (Pure)

Abstract

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 Š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 ≤ 2n/7. Our algorithm has a quadratic running time.
Original languageEnglish
Title of host publicationProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
PublisherSociety for Industrial and Applied Mathematics
Publication date2024
Pages1194-1240
ISBN (Electronic)978-1-61197-791-2
DOIs
Publication statusPublished - 2024
Event2024 Annual ACM-SIAM Symposium on Discrete Algorithms - Alexandria, United States
Duration: 7 Jan 202410 Jan 2024

Conference

Conference2024 Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityAlexandria
Period07/01/202410/01/2024

Fingerprint

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

Cite this