2024/10/29 by P. Francis, Abraham M. Illickan, Francis, P. +5
Computer Science · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2410.21808
We show that every planar triangulation on n vertices has a maximal independent set of size at most n/3. This affirms a conjecture by Botler, Fernandes and Gutiérrez [Electron. J. Comb., 2024], which in turn would follow if an open question of Goddard and Henning [Appl. Math. Comput., 2020] which asks if every planar triangulation has three disjoint maximal independent sets were answered in the affirmative. 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 n/3, but restricted to triangulations.