numero domatico

En la teoría de grafos , una partición dómatica de un grafo es una partición de en conjuntos disjuntos ,,, ... , tal que cada V _i 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 consta de los vértices amarillos, consta de los vértices verdes y consta de los vértices azules.${\ estilo de visualización G = (V, E)}$${\ estilo de visualización V}$${\displaystyle V_{1}}$${\displaystyle V_{2}}$${\displaystyle V_{K}}$${\displaystyle V_{1}}$${\displaystyle V_{2}}$${\displaystyle V_{3}}$

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. El gráfico 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 repasamos un 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 . Que conste 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 como máximo en un conjunto dominante (disjunción). Por lo tanto, hay a lo sumo conjuntos dominantes disjuntos.${\displaystyle \delta }$${\displaystyle G}$${\displaystyle G}$${\displaystyle \delta +1}$${\displaystyle v}$${\displaystyle \delta }$${\displaystyle N}$${\displaystyle v}$${\displaystyle V_{i}}$${\displaystyle N}$${\displaystyle N}$${\displaystyle V_{i}}$${\displaystyle |N|=\delta +1}$

El grafo de la figura tiene grado mínimo , y por lo tanto su número domático es como máximo 3. Por 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.${\displaystyle \delta =2}$

Si no hay un 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 débil 2-coloración. Alternativamente, (1) un conjunto independiente máximo es un conjunto dominante, y (2) el complemento de un conjunto independiente máximo también es un conjunto dominante si no hay vértices aislados.${\displaystyle \delta }$

Una partición domática

2 colores débiles