En teoría de grafos , una partición domática de un grafo es una partición de en conjuntos disjuntos , ,,..., tal que cada Vi es un conjunto dominante para G. La figura de la derecha muestra una partición domática de un gráfico; aquí el conjunto dominante está formado por los vértices amarillos, por los vértices verdes y por los vértices azules.
El número domático es el tamaño máximo de una partición domática, es decir, el número máximo de conjuntos dominantes disjuntos. La gráfica de la figura tiene el número domático 3. Es fácil ver que el número domático es al menos 3 porque hemos presentado una partición domática de tamaño 3. Para ver que el número domático es como máximo 3, primero revisamos una partición simple límite superior.
Sea el grado mínimo de la gráfica . El número domático de es como máximo . Para ver esto, considere un vértice de grado . Consistamos de y sus vecinos. Sabemos que (1) cada conjunto dominante debe contener al menos un vértice en (dominación), y (2) cada vértice en está contenido en como máximo un conjunto dominante (desunión). Por lo tanto, existen como mucho conjuntos dominantes disjuntos.
La gráfica de la figura tiene un grado mínimo y, por lo tanto, su número domático es como máximo 3. Por lo tanto, hemos demostrado que su número domático es exactamente 3; La figura muestra una partición domática de tamaño máximo.
Si no hay ningún vértice aislado en el gráfico (es decir, ≥ 1), entonces el número domático es al menos 2. Para ver esto, tenga en cuenta que (1) una coloración débil de 2 es una partición domática si no hay un vértice aislado , y (2) cualquier gráfico tiene una coloración 2 débil. Alternativamente, (1) un conjunto máximo independiente es un conjunto dominante, y (2) el complemento de un conjunto máximo independiente también es un conjunto dominante si no hay vértices aislados.
La figura de la derecha muestra una 2-coloración débil, que también es una partición domática de tamaño 2: los nodos oscuros son un conjunto dominante y los nodos claros son otro conjunto dominante (los nodos claros forman un conjunto independiente máximo). Consulte coloración débil para obtener más información.
Encontrar una partición domática de tamaño 1 es trivial: let . Encontrar una partición domática de tamaño 2 (o determinar que no existe) es fácil: verifique si hay nodos aislados y, si no, busque una partición de 2 colores débil.
Sin embargo, encontrar una partición domática de tamaño máximo es computacionalmente difícil. Específicamente, el siguiente problema de decisión , conocido como problema de números domáticos , es NP-completo : dado un gráfico y un número entero , determine si el número domático de es al menos . Por lo tanto, el problema de determinar el número domático de un gráfico dado es NP-difícil , y el problema de encontrar una partición domática de tamaño máximo también es NP-difícil.
Existe un algoritmo de aproximación en tiempo polinómico con garantía de aproximación logarítmica, [1] es decir, es posible encontrar una partición domática cuyo tamaño esté dentro de un factor del óptimo.
Sin embargo, bajo supuestos plausibles de la teoría de la complejidad, no existe un algoritmo de aproximación de tiempo polinomial con un factor de aproximación sublogarítmico. [1] Más específicamente, un algoritmo de aproximación en tiempo polinomial para partición domática con el factor de aproximación para una constante implicaría que todos los problemas en NP se pueden resolver en un tiempo ligeramente superpolinomial .
Sea G = ( U ∪ V , E ) un gráfico bipartito sin nodos aislados; todas las aristas son de la forma { u , v } ∈ E con u ∈ U y v ∈ V . Entonces { U , V } es a la vez una partición de vértice de 2 colores y una partición domática de tamaño 2; los conjuntos U y V son conjuntos dominantes independientes. El número cromático de G es exactamente 2; no hay coloración del vértice 1. El número domático de G es al menos 2. Es posible que exista una partición domática mayor; por ejemplo, el gráfico bipartito completo K n , n para cualquier n ≥ 2 tiene un número domático n .
