Sobre Conjuntos Dominantes Eficientes em Grafos / On the Efficient Dominating Sets in Graphs
AUTOR(ES)
Rommel Teodoro de Oliveira
DATA DE PUBLICAÇÃO
2009
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
ASSUNTO(S)
dominating sets, efficient dominating sets, n p-complete problems conjuntos dominates, conjuntos dominantes eficientes, problemas n pcompletos ciencia da computacao
