Conjunto dominante fraccional

En teoría de grafos , un conjunto dominante fraccionario es una generalización del concepto de conjunto dominante que permite asignar pesos fraccionarios a los vértices entre 0 y 1, en lugar de una pertenencia binaria. Esta relajación transforma el problema de dominación en un problema de programación lineal , lo que suele proporcionar límites más precisos y permite un cálculo en tiempo polinomial.

Dejar${\displaystyle G=(V,E)}$ser una gráfica. Una función dominante fraccionaria es una función${\displaystyle f:V\to [0,1]}$de tal manera que para cada vértice${\displaystyle v\in V}$, la suma de${\displaystyle f}$sobre el barrio cerrado${\displaystyle N[v]}$es al menos 1: ^{[ 1 ] [ 2 ]}

${\displaystyle \sum _{u\in N[v]}f(u)\geq 1}$

El número de dominación fraccionaria${\displaystyle \gamma _{f}(G)}$es el peso total mínimo de una función dominante fraccionaria:

${\displaystyle \gamma _{f}(G)=\min \left\{\sum _{v\in V}f(v)\right\}}$

Para cualquier gráfico${\displaystyle G}$, el número de dominación fraccionaria satisface: ^{[ 1 ]}

${\displaystyle \gamma _ {f}(G)\leq \gamma (G)\leq \Gamma (G)\leq \Gamma _ {f}(G)}$

dónde${\displaystyle \gamma (G)}$es el número de dominación ,${\displaystyle \Gamma (G)}$es el número de dominación superior, y${\displaystyle \Gamma _{f}(G)}$es el número de dominación fraccionaria superior.

El número de dominación fraccionaria se puede calcular como la solución de un programa lineal utilizando la dualidad fuerte . ^{[ 2 ]}

Para cualquier gráfico${\displaystyle G}$con${\displaystyle n}$vértices, grado mínimo${\displaystyle \delta }$y grado máximo${\displaystyle \Delta }$: ^{[ 2 ]}

${\displaystyle {\frac {n}{\Delta +1}}\leq \gamma _{f}(G)\leq {\frac {n}{\delta +1}}}$

Para cualquier gráfico${\displaystyle G}$, el número de dominación de aristas fraccionarias es igual al número de dominación del gráfico de líneas : ^{[ 3 ]}

${\displaystyle \gamma '_{f}(G)=\gamma (L(G))}$

Para un grafo k -regular con${\displaystyle n}$vértices y${\displaystyle k\geq 1}$: ^{[ 1 ] [ 4 ]}

${\displaystyle \gamma _{f}(G)={\frac {n}{k+1}}}$

Para el grafo bipartito completo${\displaystyle K_{r,s}}$: ^{[ 2 ]}

${\displaystyle \gamma _{f}(K_{r,s})={\frac {r(s-1)+s(r-1)}{rs-1}}}$

Para el gráfico cíclico${\displaystyle C_{n}}$: ^{[ 3 ]}

${\displaystyle \gamma _{f}(C_{n})={\frac {n}{3}}}$

Para el grafo de ruta${\displaystyle P_{n}}$: ^{[ 3 ]}

${\displaystyle \gamma _{f}(P_{n})=\left\lceil {\frac {n}{3}}\right\rceil }$

Para el gráfico de la corona${\displaystyle H_{n,n}}$: ^{[ 3 ]}

${\displaystyle \gamma _{f}(H_{n,n})=2}$

Para el gráfico de la rueda${\displaystyle W_{n}}$con${\displaystyle n>3}$vértices: ^{[ 3 ]}

${\displaystyle \gamma _ {f} (W_ {n}) = 1}$

Varias clases de grafos tienen${\displaystyle \gamma _{f}(G)=\gamma (G)}$: ^{[ 2 ]}

• Árboles
• Gráficos de bloques (gráficos donde cada bloque está completo)
• Gráficos fuertemente cordales

Para el producto fuerte de grafos${\displaystyle G\boxtimes H}$: ^{[ 2 ]}

${\displaystyle \gamma _{f}(G\boxtimes H)=\gamma _{f}(G)\cdot \gamma _{f}(H)}$

Para el producto cartesiano de grafos${\displaystyle G\square H}$( Conjetura de Vizing , versión fraccionaria): ^{[ 2 ]}

${\displaystyle \gamma _{f}(G\square H)\geq \gamma _{f}(G)\cdot \gamma _{f}(H)}$

Dado que el número de dominación fraccionaria puede formularse como un programa lineal, puede calcularse en tiempo polinomial, a diferencia del número de dominación estándar, cuyo cálculo es NP-difícil . ^{[ 2 ]}

Una función de k-dominancia de distancia fraccionaria generaliza el concepto al requerir que para cada vértice${\displaystyle v}$, la suma sobre su distancia-${\displaystyle k}$vecindario${\displaystyle N_{k}[v]}$(vértices a distancia como máximo${\displaystyle k}$de${\displaystyle v}$) es al menos uno. El número de k-dominación de distancia fraccionaria correspondiente se denota${\displaystyle \gamma _{kf}(G)}$. ^{[ 4 ]}

Para${\displaystyle k}$-gráficos regulares y valores específicos de${\displaystyle k}$Existen fórmulas exactas. Por ejemplo, para ciclos${\displaystyle C_{n}}$: ^{[ 4 ]}

${\displaystyle \gamma _{kf}(C_{n})={\frac {n}{2k+1}}}$

Una función dominante fraccionaria eficiente satisface

${\displaystyle \sum _{u\in N[v]}f(u)=1}$

para todos los vértices${\displaystyle v}$No todos los grafos admiten funciones dominantes fraccionarias eficientes. ^{[ 2 ]}

Una función dominante total fraccionaria requiere que para cada vértice${\displaystyle v}$, la suma sobre su vecindario abierto${\displaystyle N(v)}$(a excepción de${\displaystyle v}$en sí mismo) es al menos uno. El número de dominación total fraccionaria se denota${\displaystyle \gamma _{ft}(G)}$. ^{[ 2 ]}

El número de dominación fraccionaria superior${\displaystyle \Gamma _{f}(G)}$es el peso máximo entre todas las funciones dominantes fraccionarias mínimas. ^{[ 2 ]}

• Conjunto dominante
• Programación lineal
• Coloreado de grafos fraccionarios