























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。