Geodesic
Independent dominating sets in planar triangulations
Fábio Botler1 ; Cristina G. Fernandes2 ; Juan Gutiérrez3
1UFRJ
2USP
3University of Engineering and Technology (UTEC)
The electronic journal of combinatorics, Tome 31 (2024) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 \(\varepsilon\) for which every near planar triangulation on \(n\) vertices contains an independent dominating set of size at most \(\varepsilon n\)? We prove that \(2/7 \leq \varepsilon \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.
DOI : 10.37236/12548
Classification : 05C69, 05C10
Mots-clés : triangulation, triangulated planar graph

Fábio Botler  1   ; Cristina G. Fernandes  2   ; Juan Gutiérrez  3

1 UFRJ
2 USP
3 University of Engineering and Technology (UTEC) 
@article{10_37236_12548,
     author = {F\'abio Botler and Cristina G. Fernandes and Juan Guti\'errez},
     title = {Independent dominating sets in planar triangulations},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {2},
     doi = {10.37236/12548},
     zbl = {1536.05347},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12548/}
}
TY  - JOUR
AU  - Fábio Botler
AU  - Cristina G. Fernandes
AU  - Juan Gutiérrez
TI  - Independent dominating sets in planar triangulations
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12548/
DO  - 10.37236/12548
ID  - 10_37236_12548
ER  - 
%0 Journal Article
%A Fábio Botler
%A Cristina G. Fernandes
%A Juan Gutiérrez
%T Independent dominating sets in planar triangulations
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12548/
%R 10.37236/12548
%F 10_37236_12548
Fábio Botler; Cristina G. Fernandes; Juan Gutiérrez. Independent dominating sets in planar triangulations. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/12548

Cité par Sources :