Maximal Independent Sets in Planar Triangulations
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The domination number of plane triangulationsJournal of Combinatorial Theory, Series B, 2020
- Planar Graphs have Independence Ratio at least 3/13The Electronic Journal of Combinatorics, 2016
- Domination in Graphs of Minimum Degree FiveGraphs and Combinatorics, 2006
- Domination in planar graphs with small diameter*Journal of Graph Theory, 2002
- Dominating Sets in Planar GraphsEuropean Journal of Combinatorics, 1996
- Domination numbers of planar graphsJournal of Graph Theory, 1996
- Paths, Stars and the Number ThreeCombinatorics, Probability and Computing, 1996
- Towards a theory of domination in graphsNetworks, 1977
- Every planar map is four colorable. Part I: DischargingIllinois Journal of Mathematics, 1977
- A lower bound for the independence number of a planar graphJournal of Combinatorial Theory, Series B, 1976