Sobre conjuntos dominantes eficientes em grafos
Carregando...
Data
2009-03-12
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
Given a graph G = (V;E) and a set of vertices D V, a vertice v 2 V is dominated by D if jN[v] \ Dj 1. When jN(v) \ Dj = 1 for all v 2 V, G is efficiently dominable. A generalization of this concept is called efficient multiple domination, which requires all vertices must be dominated by a set D V exactly k times. The aim of this dissertation is to study these topics, describing the theoretical knowledge needed for advanced
researches. For this reason, many of the theorems and its proofs are detailed. Furthermore, some results on the efficient multiple domination are presented, including bounds for
the size of efficient k-dominating sets, the complement and iterated line graphs of efficiently (r + 1)-dominable r-regular graphs and a N P-completeness proof for the efficient multiple domination problem in arbitrary graphs. It is expected that this work contribute to the development of future researches on the efficient domination and in the resolution of some open problems.
Descrição
Citação
OLIVEIRA, Rommel Teodoro de. Sobre conjuntos dominantes eficientes em grafos. 2009. 130 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2009.