Independent dominating sets in planar triangulations

EUROCOMB’23

Abstract
In 1996, Matheson and Tarjan proved that every planar triangulation on \(n\) vertices contains a dominating set, i.e., a set \(S\) that contains a neighbor of every vertex not in \(S\), of size at most \(n/3\), and conjectured that this upper bound can be reduced to \(n/4\) when $n$ is sufficiently large. In this paper, we consider the analogous problem for independent dominating sets: What is the minimum \(ε\) for which every planar triangulation on \(n\) vertices contains an independent dominating set of size at most \(ε n\)? We prove that \(2/7 \leq ε \leq 3/8\).

Pages:
163–168
References

Oleg V. Borodin. On acyclic colorings of planar graphs. Discrete Math., 25(3):211-236, 1979.
https://doi.org/10.1016/0012-365X(79)90077-3

Christiane N. Campos and Yoshiko Wakabayashi. On dominating sets of maximal outerplanar graphs. Discrete Appl. Math. , 161(3):330-335, 2013.
https://doi.org/10.1016/j.dam.2012.08.023

Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg, fourth edition, 2010.
https://doi.org/10.1007/978-3-642-14279-6

Wayne Goddard and Michael A. Henning. Independent domination in graphs: a survey and recent results. Discrete Math., 313(7):839-854, 2013.
https://doi.org/10.1016/j.disc.2012.11.031

Wayne Goddard and Michael A. Henning. Independent domination, colorings and the fractional idomatic number of a graph. Appl. Math. Comput., 382:125340, 8, 2020.
https://doi.org/10.1016/j.amc.2020.125340

Erika L. C. King and Michael J. Pelsmajer. Dominating sets in plane triangulations. Discrete Math., 310(17-18):2221-2230, 2010.
https://doi.org/10.1016/j.disc.2010.03.022

Zepeng Li, Enqiang Zhu, Zehui Shao, and Jin Xu. On dominating sets of maximal outerplanar and planar graphs. Discrete Appl. Math., 198:164-169, 2016.
https://doi.org/10.1016/j.dam.2015.06.024

Lesley R. Matheson and Robert E. Tarjan. Dominating sets in planar graphs. European J. Combin., 17(6):565-568, 1996.
https://doi.org/10.1006/eujc.1996.0048

Michael D. Plummer, Dong Ye, and Xiaoya Zha. Dominating plane triangulations. Discrete Appl. Math., 211:175-182, 2016.
https://doi.org/10.1016/j.dam.2016.04.011

Michael D. Plummer, Dong Ye, and Xiaoya Zha. Dominating maximal outerplane graphs and Hamiltonian plane triangulations. Discrete Appl. Math., 282:162-167, 2020.
https://doi.org/10.1016/j.dam.2019.12.003

Shin-ichi Tokunaga. Dominating sets of maximal outerplanar graphs. Discrete Appl. Math., 161(18):3097-3099, 2013.
https://doi.org/10.1016/j.dam.2013.06.025

Simon pacapan. The domination number of plane triangulations. J. Combin. Theory Ser. B, 143:42-64, 2020.
https://doi.org/10.1016/j.jctb.2019.11.005

Igor E. Zverovich and Vadim E. Zverovich. An induced subgraph characterization of domination perfect graphs. J. Graph Theory, 20(3):375-395, 1995.
https://doi.org/10.1002/jgt.3190200313

Metrics

0

Views

0

PDF views