El conjunto dominante de un grafo G = (V, E) es un subconjunto V' de V tal que cada vértice que no pertenezca a V' está unido a (al menos) un miembro de V'. El número dominante γ(G) es el cardinal del menor conjunto dominante de G.
El problema de la dominación en grafos ha sido estudiado desde la década de los cincuenta, pero el interés por esta área creció significativamente a mediados de los setenta (Hedetniemi y Laskar, 1990).
Problemas relacionados
El problema del conjunto dominante se centra en decidir si γ(G) ≤ K para un K determinado; se trata de un problema NP-completo (Garey y Johnson, 1979). Otro problema NP-completo relacionado con la dominación es el domatic number problem, en el que se debe particionar el conjunto de vértices de un grafo en un número determinado (dado) de conjuntos dominantes; el máximo número de conjuntos en cualquier partición posible es el domatic number del grafo.
La conjetura de Vizing relaciona el número de dominación del producto cartesiano de dos grafos con el número de dominación de sus factores.
Los conjuntos dominantes están estrechamente relacionados con los conjuntos independientes: un conjunto independiente maximal de un grafo es necesariamente un conjunto dominante. Sin embargo, los conjuntos dominantes no son necesariamente independientes. Si S es un conjunto conexo y dominante (connected dominating set en inglés, CDS), se puede formar un árbol de expansión de G en el que S forme un conjunto de nodos no-hojas del árbol; análogamente, si T es un árbol de expansión en un grafo con más de 2 vértices, los nodos no-hojas de T forman un conjunto conexo y dominante. Así, encontrar conjuntos conexos y dominantes mínimos es equivalente a encontrar árboles de expansión con el máximo número posible de hojas.
Un conjunto dominante total es un conjunto de vértices tal que todos los vértices del grafo (incluidos los vértices del conjunto dominante) tienen un vecino en el conjunto dominante.
Ejemplo
Sea G un ciclo de 8 vértices vi, 0 ≤ i < 8, con vi adyacente a vi - 1 (mod 8) y vi + 1 (mod 8). Entonces, G puede ser dominado con 3 vértices, por ejemplo {v0, v3, v6}. Cualquier otro vértice es adyacente a una de estas tres posiciones. Esto es, γ(G) = 3. Sin embargo, el menor conjunto dominante total contiene 4 vértices, por ejemplo {v0, v1, v4, v5}. El menor conjunto conexo y dominante para G contiene 6 vértices, por ejemplo {v0, v1, v2, v3, v4, v5}. Y el conjunto dominante minimal más grande de G tiene 4 vértices: {v0, v2, v4, v6}.
Referencias
Garey, M.; Johnson, D. (1979). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5. OCLC 11745039.
Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998). Fundamentals of Domination in Graphs. Marcel Dekker. ISBN 0-8247-0033-3. OCLC 37903553.
Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998). Domination in Graphs: Advanced Topics. Marcel Dekker. ISBN 0-8247-0034-1. OCLC 38201061.
Hedetniemi, S. T.; Laskar, R. C. (1990), "Bibliography on domination in graphs and some basic definitions of domination parameters", Discrete Mathematics 86(1–3): 257–277, doi:10.1016/0012-365X(90)90365-O
Datos:Q2915204
Multimedia:Dominating set (graph theory)
Agosto 05, 2021
conjunto, dominante, conjunto, dominante, grafo, subconjunto, cada, vértice, pertenezca, está, unido, menos, miembro, número, dominante, cardinal, menor, conjunto, dominante, problema, dominación, grafos, sido, estudiado, desde, década, cincuenta, pero, interé. El conjunto dominante de un grafo G V E es un subconjunto V de V tal que cada vertice que no pertenezca a V esta unido a al menos un miembro de V El numero dominante g G es el cardinal del menor conjunto dominante de G El problema de la dominacion en grafos ha sido estudiado desde la decada de los cincuenta pero el interes por esta area crecio significativamente a mediados de los setenta Hedetniemi y Laskar 1990 Problemas relacionados EditarEl problema del conjunto dominante se centra en decidir si g G K para un K determinado se trata de un problema NP completo Garey y Johnson 1979 Otro problema NP completo relacionado con la dominacion es el domatic number problem en el que se debe particionar el conjunto de vertices de un grafo en un numero determinado dado de conjuntos dominantes el maximo numero de conjuntos en cualquier particion posible es el domatic number del grafo La conjetura de Vizing relaciona el numero de dominacion del producto cartesiano de dos grafos con el numero de dominacion de sus factores Los conjuntos dominantes estan estrechamente relacionados con los conjuntos independientes un conjunto independiente maximal de un grafo es necesariamente un conjunto dominante Sin embargo los conjuntos dominantes no son necesariamente independientes Si S es un conjunto conexo y dominante connected dominating set en ingles CDS se puede formar un arbol de expansion de G en el que S forme un conjunto de nodos no hojas del arbol analogamente si T es un arbol de expansion en un grafo con mas de 2 vertices los nodos no hojas de T forman un conjunto conexo y dominante Asi encontrar conjuntos conexos y dominantes minimos es equivalente a encontrar arboles de expansion con el maximo numero posible de hojas Un conjunto dominante total es un conjunto de vertices tal que todos los vertices del grafo incluidos los vertices del conjunto dominante tienen un vecino en el conjunto dominante Ejemplo EditarSea G un ciclo de 8 vertices vi 0 i lt 8 con vi adyacente a vi 1 mod 8 y vi 1 mod 8 Entonces G puede ser dominado con 3 vertices por ejemplo v0 v3 v6 Cualquier otro vertice es adyacente a una de estas tres posiciones Esto es g G 3 Sin embargo el menor conjunto dominante total contiene 4 vertices por ejemplo v0 v1 v4 v5 El menor conjunto conexo y dominante para G contiene 6 vertices por ejemplo v0 v1 v2 v3 v4 v5 Y el conjunto dominante minimal mas grande de G tiene 4 vertices v0 v2 v4 v6 Referencias EditarGarey M Johnson D 1979 Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman ISBN 0 7167 1045 5 OCLC 11745039 Haynes Teresa W Hedetniemi Stephen Slater Peter 1998 Fundamentals of Domination in Graphs Marcel Dekker ISBN 0 8247 0033 3 OCLC 37903553 Haynes Teresa W Hedetniemi Stephen Slater Peter 1998 Domination in Graphs Advanced Topics Marcel Dekker ISBN 0 8247 0034 1 OCLC 38201061 Hedetniemi S T Laskar R C 1990 Bibliography on domination in graphs and some basic definitions of domination parameters Discrete Mathematics 86 1 3 257 277 doi 10 1016 0012 365X 90 90365 O Datos Q2915204 Multimedia Dominating set graph theory Obtenido de https es wikipedia org w index php title Conjunto dominante amp oldid 135198917, wikipedia, wiki, leyendo, leer, libro, biblioteca,
