Dominación en gráficas

Abstract

Given any finite graph G = (V; A), a dominating set of G is a subset D V such as every vertex v 2 V not in D is adjacent to some vertex in D. The domination number (G) of a graph G is the minimum cardinality of a dominating set of G. Given a graph G and a positive integer k, the problem about deciding if G has a dominating set of size k is NP-complete. In this paper we will establish some bounds for the domination number (G) in terms of order, size, degree and other parameters and we will give some examples and interesting problems that motivate the study of this problem.

Dada cualquier grafica finita G = (V; A), un conjunto dominador de G es un subconjunto D V tal que todo vértice v 2 V que no esté en D es adyacente a algún vértice en D. El número de dominación (G) de una gráfica G es la menor cardinalidad de un conjunto dominador de G. Dada una gráfica G y un entero positivo k, el problema de decidir si G tiene un conjunto dominador de tamaño k es NP-completo. En este trabajo vamos a establecer algunas cotas para el número de dominación (G) en términos del orden, tamaño, grado y otros parámetros y daremos varios ejemplos y problemas interesantes que motivan el estudio de este problema.