Back to Search Start Over

Independent dominating sets in planar triangulations

Authors :
Botler, Fábio
Fernandes, Cristina G.
Gutiérrez, Juan
Publication Year :
2023

Abstract

In 1996, Matheson and Tarjan proved that every near planar triangulation on $n$ vertices contains a dominating set of size at most $n/3$, and conjectured that this upper bound can be reduced to $n/4$ for planar triangulations when $n$ is sufficiently large. In this paper, we consider the analogous problem for independent dominating sets: What is the minimum $\epsilon$ for which every near planar triangulation on $n$ vertices contains an independent dominating set of size at most $\epsilon n$? We prove that $2/7 \leq \epsilon \leq 5/12$. Moreover, this upper bound can be improved to $3/8$ for planar triangulations, and to $1/3$ for planar triangulations with minimum degree 5.<br />Comment: 9 pages

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2308.02754
Document Type :
Working Paper