María Gracia Cornet -GRACE- (Problemas de dominación en grafos de Johnson)

web: https://www.riimat.com Resumen: Dados $n,r\in \mathbb{N}$ con $n\ge r$, el grafo de Johnson $J(n,r)$ es el grafo cuyos vértices son los subconjuntos de tamaño $r$ de $[n]=\{1,2,\ldots,n\}$, donde dos vértices $u$ y $v$ son adyacentes si y solo si $|u\cap v|=r-1$. Un conjunto dominante de un grafo $G$ es un subconjunto $D\subseteq V(G)$ tal que todo vértice que no pertenece a $D$ tiene un vecino en $D$. El cardinal mínimo de un conjunto dominante se denomina número de dominación de $G$ y se denota por $\gamma(G)$. Un conjunto dominante total de un grafo $G$ es un subconjunto $D\subseteq V(G)$ tal que todo vértice de $G$ tiene un vecino en $D$. El cardinal mínimo de un conjunto dominante total se denomina número de dominación total de $G$ y se denota por $\gamma_t(G)$. En esta charla discutiremos sobre la dominación y la dominación total en los grafos de Johnson $J(n,r)$. Determinamos los valores exactos de ambos parámetros para $J(n,2)$ y $J(n,3)$. En el caso $r=3$, nuestro enfoque traduce el problema de calcular $\gamma(J(n,3))$ y $\gamma_t(J(n,3))$ a problemas de cubrimientos de aristas mediante triángulos en grafos de orden $n$ cuyo número de independencia es a lo sumo $2$. Apoya: https://www.sivar.com.co/ https://coltek.com.co/