Independent Domination Number of Planar Triangulations

P. Francis; Abraham M. Illickan; Lijo M. Jose; Deepak Rajendraprasad

doi:10.1002/jgt.23285

Independent Domination Number of Planar Triangulations

P. Francis
, Abraham M. Illickan
, Lijo M. Jose^*
, Deepak Rajendraprasad

^*Corresponding author for this work

School of Computer Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

We show that every planar triangulation on (Formula presented.) vertices has a maximal independent set of size at most (Formula presented.). 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 (Formula presented.), but restricted to triangulations.

Original language	English
Pages (from-to)	426-430
Number of pages	5
Journal	Journal of Graph Theory
Volume	110
Issue number	4
DOIs	https://doi.org/10.1002/jgt.23285
Publication status	Accepted/In press - 2025

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.23285

Cite this

@article{d8c2eb64c19c4bfc87a3bd56f7164344,

title = "Independent Domination Number of Planar Triangulations",

abstract = "We show that every planar triangulation on (Formula presented.) vertices has a maximal independent set of size at most (Formula presented.). This affirms a conjecture by Botler, Fernandes, and Guti{\'e}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 (Formula presented.), but restricted to triangulations.",

author = "P. Francis and Illickan, \{Abraham M.\} and Jose, \{Lijo M.\} and Deepak Rajendraprasad",

note = "Publisher Copyright: {\textcopyright} 2025 Wiley Periodicals LLC.",

year = "2025",

doi = "10.1002/jgt.23285",

language = "English",

volume = "110",

pages = "426--430",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Independent Domination Number of Planar Triangulations

AU - Francis, P.

AU - Illickan, Abraham M.

AU - Jose, Lijo M.

AU - Rajendraprasad, Deepak

PY - 2025

Y1 - 2025

N2 - We show that every planar triangulation on (Formula presented.) vertices has a maximal independent set of size at most (Formula presented.). 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 (Formula presented.), but restricted to triangulations.

AB - We show that every planar triangulation on (Formula presented.) vertices has a maximal independent set of size at most (Formula presented.). 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 (Formula presented.), but restricted to triangulations.

UR - https://www.scopus.com/pages/publications/105010768241

UR - https://www.scopus.com/pages/publications/105010768241#tab=citedBy

U2 - 10.1002/jgt.23285

DO - 10.1002/jgt.23285

M3 - Article

AN - SCOPUS:105010768241

SN - 0364-9024

VL - 110

SP - 426

EP - 430

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

Independent Domination Number of Planar Triangulations

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this