Early View
ARTICLE

Independent Domination Number of Planar Triangulations

P. Francis

P. Francis

Department of Mathematics SAS, VIT-AP University, Amaravati, Andhra Pradesh, India

Search for more papers by this author
Abraham M. Illickan

Abraham M. Illickan

Department of Computer Science, University of California, Irvine, California, USA

Search for more papers by this author
Lijo M. Jose

Corresponding Author

Lijo M. Jose

Department of Information Technology, Manipal Institute of Technology Bengaluru, Manipal Academy of Higher Education, Manipal, Karnataka, India

Correspondence: Lijo M. Jose ([email protected])

Search for more papers by this author
Deepak Rajendraprasad

Deepak Rajendraprasad

Department of Computer Science, Indian Institute of Technology Palakkad, Kanjikode, Kerala, India

Search for more papers by this author
First published: 17 July 2025

ABSTRACT

We show that every planar triangulation on n $n$ vertices has a maximal independent set of size at most n / 3 $n/3$ . 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 n / 3 $n/3$ , but restricted to triangulations.

Data Availability Statement

Data sharing is not applicable to this article, as no datasets were generated or analyzed during the current study.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.