| Texto completo | |
| Autor(es): |
Número total de Autores: 2
|
| Afiliação do(s) autor(es): | [1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] Univ Sao Paulo, Inst Math & Stat, BR-05508090 Sao Paulo - Brazil
Número total de Afiliações: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE APPLIED MATHEMATICS; v. 161, n. 3, p. 330-335, FEB 2013. |
| Citações Web of Science: | 13 |
| Resumo | |
A dominating set of a graph is a set S of vertices such that every vertex in the graph is either in S or is adjacent to a vertex in S. The domination number of a graph G, denoted gamma(G), is the minimum cardinality of a dominating set of G. We show that if G is an n-vertex maximal outerplanar graph, then gamma (G) <= (n + t)/4, where t is the number of vertices of degree 2 in G. We show that this bound is tight for all t >= 2. Upper-bounds for gamma(G) are known for a few classes of graphs. (C) 2012 Elsevier B.V. All rights reserved. (AU) | |
| Processo FAPESP: | 06/60177-8 - Aspectos teoricos, estruturais e de otimizacao de alguns problemas em grafos. |
| Beneficiário: | Christiane Neme Campos |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |