Conjunto dominante

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 minimal. 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