Conjunto dominante romano

En teoría de grafos , un conjunto dominante romano (RDS) es un tipo especial de conjunto dominante inspirado en las estrategias históricas de defensa militar del Imperio Romano . Este concepto modela un escenario donde las ciudades (vértices) pueden ser defendidas por legiones estacionadas dentro de la ciudad o en ciudades vecinas. Una ciudad se considera segura si tiene al menos una legión estacionada allí, o si no tiene legiones pero es adyacente a una ciudad que tiene al menos dos legiones, lo que permite enviar una legión para la defensa mientras la ciudad original permanece protegida.

El número de dominación romana de un gráfico mide el número total mínimo de legiones necesarias para proteger todas las ciudades según esta estrategia.

Dejar${\displaystyle G=(V,E)}$ser un gráfico. Una función dominante romana (FDR) es una función${\displaystyle f:V\to \{0,1,2\}}$de tal manera que para cada vértice${\displaystyle v}$con${\displaystyle f(v)=0}$, existe un vértice${\displaystyle u}$adyacente a${\displaystyle v}$con${\displaystyle f(u)=2}$. ^{[ 1 ]}

El peso de una función dominante romana${\displaystyle f}$es${\displaystyle w(f)=\sum _ {v\in V}f(v)}$. El número de dominación romana${\displaystyle \gamma _{R}(G)}$es el peso mínimo entre todas las funciones dominantes romanas para${\displaystyle G}$.

De forma equivalente, dejemos${\ Displaystyle (V_ {0}, V_ {1}, V_ {2})}$ser una partición ordenada de${\displaystyle V}$dónde${\displaystyle V_{i}=\{v\in V:f(v)=i\}}$. Entonces${\displaystyle f}$es una función dominante romana si y solo si cada vértice en${\displaystyle V_{0}}$es adyacente a al menos un vértice en${\displaystyle V_{2}}$. ^{[ 1 ]}

Para ver el gráfico completo${\displaystyle K_{n}}$con${\displaystyle n\geq 2}$,${\displaystyle \gamma _{R}(K_{n})=2}$, logrado asignando 2 a cualquier vértice y 0 a todos los demás.

Para el grafo de ruta${\displaystyle P_{n}}$y gráfico cíclico${\displaystyle C_{n}}$,${\displaystyle \gamma _{R}(P_{n})=\gamma _{R}(C_{n})=\lceil 2n/3\rceil }$. ^{[ 1 ]}

Para el grafo vacío${\displaystyle {\overline {K}}_{n}}$,${\displaystyle \gamma _{R}({\overline {K}}_{n})=n}$, ya que a cada vértice se le debe asignar al menos 1.

Para el grafo n -partito completo${\displaystyle K_{m_{1},m_{2},\dots ,m_{n}}}$con tamaños de partición${\displaystyle m_{1}\leq m_{2}\leq \dots \leq m_{n}}$: ^{[ 1 ]}

• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=2}$si${\displaystyle m_{1}=1}$.
• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=3}$si${\displaystyle m_{1}=2}$.
• ${\displaystyle \gamma _{R}(K_{m_{1},\dots ,m_{n}})=4}$si${\displaystyle m_{1}\geq 3}$.

Cockayne et al. establecieron varias propiedades de la dominación romana: ^{[ 1 ]}

• Para cualquier gráfico${\displaystyle G}$,${\displaystyle \gamma (G)\leq \gamma _{R}(G)\leq 2\gamma (G)}$, dónde${\displaystyle \gamma (G)}$es el número de dominación .
• ${\displaystyle \gamma (G)=\gamma _{R}(G)}$si y solo si${\displaystyle G}$es el gráfico vacío.
• Si${\displaystyle G}$tiene un vértice de grado${\displaystyle n-1}$, entonces${\displaystyle \gamma _{R}(G)=2}$.
• Para cualquier función dominante romana${\displaystyle f=(V_{0},V_{1},V_{2})}$:
  • El subgrafo inducido por${\displaystyle V_{1}}$tiene un grado máximo de como máximo 1.
  • Sin uniones de borde${\displaystyle V_{1}}$y${\displaystyle V_{2}}$.
  • Cada vértice en${\displaystyle V_{0}}$es adyacente a como máximo dos vértices en${\displaystyle V_{1}}$.
  • ${\displaystyle V_{2}}$es un conjunto dominante para el subgrafo inducido por${\displaystyle V_{0}\cup V_{2}}$.

Un gráfico${\displaystyle G}$se llama gráfico romano si${\displaystyle \gamma _{R}(G)=2\gamma (G)}$. ^{[ 2 ]} Esto ocurre si y solo si${\displaystyle G}$tiene una función dominante romana de peso mínimo con${\displaystyle V_{1}=\emptyset }$.

El valor de dominación romana de un vértice extiende el concepto de dominación romana al considerar cuántas funciones de dominación romana mínima asignan valores positivos a ese vértice. ^{[ 3 ]}

Para un gráfico${\displaystyle G}$, dejar${\displaystyle F}$ser el conjunto de todos${\displaystyle \gamma _{R}(G)}$-funciones (funciones romanas dominantes de peso mínimo). Para un vértice${\displaystyle v\in V}$, el valor de la dominación romana${\displaystyle R_{G}(v)}$se define como:

${\displaystyle R_{G}(v)=\sum _{f\in F}f(v)}$

Se conocen algunas propiedades básicas del valor de la dominación romana: ^{[ 3 ]}

• ${\displaystyle 0\leq R_{G}(v)\leq 2\tau _{R}(G)}$, dónde${\displaystyle \tau _{R}(G)}$es el número de${\displaystyle \gamma _{R}(G)}$-funciones
• ${\displaystyle \sum _{v\in V(G)}R_{G}(v)=\tau _{R}(G)\gamma _{R}(G)}$
• Si existe un mapeo de isomorfismo de grafos vértice${\displaystyle v}$en${\displaystyle G}$al vértice${\displaystyle v'}$en${\displaystyle G'}$, entonces${\displaystyle R_{G}(v)=R_{G'}(v')}$

Se han establecido varios resultados extremos para los números de dominación romana.

Para cualquier conectado${\displaystyle n}$-grafo de vértices${\displaystyle G}$con${\displaystyle n\geq 3}$,${\displaystyle \gamma _{R}(G)\leq 4n/5}$. ^{[ 4 ]} La igualdad se cumple si y solo si${\displaystyle G}$es${\displaystyle C_{5}}$o obtenido de${\displaystyle n/5}$copias de${\displaystyle P_{5}}$agregando un subgrafo conectado al conjunto de centros.

Para cualquier${\displaystyle n}$-grafo de vértices${\displaystyle G}$con${\displaystyle n\geq 3}$,${\displaystyle 5\leq \gamma _{R}(G)+\gamma _{R}({\overline {G}})\leq n+3}$. ^{[ 4 ]}

Para cualquier${\displaystyle n}$-grafo de vértices${\displaystyle G}$con${\displaystyle n\geq 160}$,${\displaystyle \gamma _{R}(G)\gamma _{R}({\overline {G}})\leq 16n/5}$. ^{[ 4 ]}

Si${\displaystyle G}$es un conectado${\displaystyle n}$-grafo de vértices con${\displaystyle \delta (G)\geq 2}$y${\displaystyle n\geq 9}$, entonces${\displaystyle \gamma _{R}(G)\leq 8n/11}$. ^{[ 4 ]}

El problema de decisión para la dominación romana es NP-completo, incluso cuando se restringe a grafos bipartitos , cordales o planares . ^{[ 1 ]} Sin embargo, existen algoritmos de tiempo polinomial para calcular el número de dominación romana en grafos de intervalos , cografos y grafos fuertemente cordales . ^{[ 2 ]}

• Conjunto dominante
• Etiquetado de gráficos