What type of study is this?

September 10, 2025

Independent Domination Number of Planar Triangulations

Key Points

Every planar triangulation has a maximal independent set of size at most k.
This finding confirms a conjecture by Botler, Fernandes, and Gutiérrez related to a known open question.
By establishing this bound, the research strengthens a key result about dominating sets in triangulated discs.
The results rely on established principles from graph theory, emphasizing the relationship between independent and dominating sets.

Abstract

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.

Bookmark

Cite This Study

Francis et al. (Thu,) studied this question.

synapsesocial.com/papers/68c1c22d54b1d3bfb60ef6b2 https://doi.org/https://doi.org/10.1002/jgt.23285

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark