Por favor, use este identificador para citar o enlazar este ítem:
http://bibliotecavirtual.dgb.umich.mx:8083/xmlui/handle/DGB_UMICH/1220
Título : | Dominación en gráficas |
Autor : | Pérez Contreras, Eric Paulí |
Asesor: | Pérez Seguí, María Luisa |
Palabras clave : | info:eu-repo/classification/cti/1 IFM-M-2015-2296 Número Conjunto Grafos |
Fecha de publicación : | dic-2015 |
Editorial : | Universidad Michoacana de San Nicolás de Hidalgo. Universidad Nacional Autónoma de México |
Resumen : | 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. |
Descripción : | Instituto de Física y Matemáticas. Facultad de Ciencias Físico Matemáticas. Unidad Morelia del Instituto de Matemáticas de la UNAM. Programa Conjunto de Maestría en Matemáticas |
URI : | http://bibliotecavirtual.dgb.umich.mx:8083/xmlui/handle/DGB_UMICH/1220 |
Aparece en las colecciones: | Maestría |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
IFM-M-2015-2296.pdf | 544.44 kB | Adobe PDF | ![]() Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.