Independent Domination Number of Planar Triangulations
ABSTRACT
We show that every planar triangulation on vertices has a maximal independent set of size at most . This affirms a conjecture by Botler, Fernandes, and Gutiérrez (Electron. J. Comb., 2024) based on an open question of Goddard and Henning (Appl. Math. Comput., 2020). Since a maximal independent set is a special type of dominating set (independent dominating set), this is a structural strengthening of a major result by Matheson and Tarjan (Eur. J. Comb., 1996) that every triangulated disc has a dominating set of size at most , but restricted to triangulations.
Open Research
Data Availability Statement
Data sharing is not applicable to this article, as no datasets were generated or analyzed during the current study.