| Texto completo | |
| Autor(es): |
Botler, Fabio
;
Fernandes, Cristina G.
;
Gutierrez, Juan
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | PROCEEDINGS OF THE 12TH EUROPEAN CONFERENCE ON COMBINATORICS, GRAPH THEORY AND APPLICATIONS, EUROCOMB 2023; v. N/A, p. 6-pg., 2023-01-01. |
| Resumo | |
In 1996, Matheson and Tarjan proved that every 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 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 planar triangulation on n vertices contains an independent dominating set of size at most epsilon n? We prove that 2/7 <= epsilon <= 3/8. (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 |