| Texto completo | |
| Autor(es): |
Botler, Fabio
;
Fernandes, Cristina G.
;
Gutierrez, Juan
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ELECTRONIC JOURNAL OF COMBINATORICS; v. 31, n. 2, p. 10-pg., 2024-04-19. |
| Resumo | |
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 S epsilon 6 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. (AU) | |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |