Conjunto dominante de independencia

En teoría de grafos , un conjunto dominante de independencia para un grafo${\displaystyle G=(V,E)}$es un subconjunto${\displaystyle D\subseteq V}$que domina un conjunto independiente dado${\displaystyle A}$de${\displaystyle G}$; es decir, cada vértice en${\displaystyle A}$está en${\displaystyle D}$o adyacente a un vértice en${\displaystyle D}$. ^{[ 1 ]} A diferencia de los conjuntos dominantes ordinarios , que deben dominar cada vértice del grafo, un conjunto dominante de independencia solo está requerido para dominar los vértices de un conjunto independiente particular.

El número de dominación de la independencia${\displaystyle i\gamma (G)}$de un gráfico${\displaystyle G}$es el máximo, sobre todos los conjuntos independientes${\displaystyle A}$de${\displaystyle G}$, del conjunto más pequeño dominante${\displaystyle A}$. ^{[ 1 ]} Dominar subconjuntos de vértices requiere potencialmente menos vértices que dominar todos los vértices, por lo que${\displaystyle i\gamma (G)\leq \gamma (G)}$para todos los gráficos${\displaystyle G}$.

La desigualdad puede ser estricta; hay gráficos${\displaystyle G}$para qué${\displaystyle i\gamma (G)<\gamma (G)}$Por ejemplo, para algún número entero${\displaystyle n}$, dejar${\displaystyle G}$sea ​​un grafo en el que los vértices son las filas y columnas de un${\displaystyle n}$-por-${\displaystyle n}$tablero, y dos de esos vértices están conectados si y solo si se intersecan. Los únicos conjuntos independientes son conjuntos de solo filas o conjuntos de solo columnas, y cada uno de ellos puede estar dominado por un solo vértice (una columna o una fila), por lo que${\displaystyle i\gamma (G)=1}$Sin embargo, para dominar todos los vértices necesitamos al menos una fila y una columna, por lo que${\displaystyle \gamma (G)=2}$Además, la relación entre${\displaystyle \gamma (G)/i\gamma (G)}$puede ser arbitrariamente grande. Por ejemplo, si los vértices de${\displaystyle G}$son todos los subconjuntos de cuadrados de un${\displaystyle n}$-por-${\displaystyle n}$tablero, entonces todavía${\displaystyle i\gamma (G)=1}$, pero${\displaystyle \gamma (G)=n}$. ^{[ 1 ]}

El número de dominación de independencia está estrechamente relacionado con la conjetura de Vizing , que establece que para todos los grafos${\displaystyle G}$y${\displaystyle H}$, el número de dominación del producto cartesiano satisface${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\cdot \gamma (H)}$. ^{[ 2 ]} Aharoni y Szabó demostraron que para todos los gráficos${\displaystyle G}$y${\displaystyle H}$, ^{[ 3 ]}

${\displaystyle \gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot \gamma (H)}$

${\displaystyle i\gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot i\gamma (H).}$

Dado que cualquier clase de grafo para la cual${\displaystyle \gamma (G)=i\gamma (G)}$Satisface automáticamente la conjetura de Vizing; esta conexión motiva el estudio de qué clases de grafos tienen esta propiedad. ^{[ 2 ]}

Para los grafos cordales , el número de dominación de independencia es igual al número de dominación:${\displaystyle \gamma (G)=i\gamma (G)}$. ^{[ 1 ]} Esto implica que la conjetura de Vizing se cumple para grafos cordales. ^{[ 3 ]} Para grafos fuertemente cordales , se cumple la misma igualdad ya que el número de dominación fraccionaria es igual al número de dominación para tales grafos. ^{[ 2 ]}

Para los cografos , el número de dominación de independencia tiene una caracterización simple:${\displaystyle i\gamma (G)}$es igual al número de componentes conexas de${\displaystyle G}$. ^{[ 2 ]} Esto se deduce de la estructura recursiva de los cografos como uniones y combinaciones: en una combinación${\displaystyle G_{1}\otimes G_{2}}$, cualquier conjunto independiente maximal está contenido en un constituyente y puede ser dominado por un único vértice del otro, dando como resultado${\displaystyle i\gamma (G)=1}$; en una unión${\displaystyle G_{1}\oplus G_{2}}$, las cifras de dominación de la independencia se suman. ^{[ 2 ]}

Calcular el número de dominación de independencia es NP-completo para varias clases de grafos, incluidos los grafos cordales (ya que la dominación ya es NP-completa para los grafos cordales) y los grafos bipartitos . También es NP-completo decidir si${\displaystyle i\gamma (G)\geq 2}$para grafos débilmente cordales . ^{[ 4 ]}

Por otro lado, existen algoritmos de tiempo polinomial para varias clases restringidas de grafos: ^{[ 2 ]}

• Gráficos fuertemente cordales
• Grafos hereditarios de distancia (y, más generalmente, grafos de rango-ancho acotado ), en${\displaystyle O(n^{3})}$tiempo
• Grafos de permutación , en tiempo polinomial
• Gráficos de ancho de árbol limitado , en${\displaystyle O(n^{3})}$tiempo

Para gráficos generales, hay un algoritmo exacto de tiempo exponencial que se ejecuta en${\displaystyle O^{*}(1,7972^{n})}$tiempo. Este algoritmo enumera todos los conjuntos independientes máximos (de los cuales hay como máximo${\displaystyle 3^{n/3}}$mediante la cota de Moon-Moser ) y encuentra un conjunto dominante mínimo para cada uno utilizando una estrategia de ramificación combinada con el emparejamiento máximo . ^{[ 2 ]}

El número de dominación bi-independiente${\displaystyle i\gamma i(G)}$de un gráfico${\displaystyle G}$es el máximo, sobre todos los conjuntos independientes${\displaystyle A}$de${\displaystyle G}$, del conjunto independiente más pequeño dominante${\displaystyle A}$Las siguientes relaciones se cumplen para cualquier grafo.${\displaystyle G}$: $${\displaystyle {\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}}$$ dónde${\displaystyle i(G)}$es el número de dominación independiente .

• Conjunto dominante independiente
• La conjetura de Vizing