Dominación, cubiertas y 2-acoplamientos en gráficas

Autor: Adrian Vázquez Avila
Coautor(es): Carlos Alfaro Montufar y Christian Rubio Montiel
Un conjunto dominante en una gráfica $G$ es un conjunto $D\subseteq V(G)$ tal que todo vértice de $G$ está en $D$ o es adyacente a algún vértice de $D$. El número de dominación de $G$, $\gamma(G)$, es la cardinalidad más pequeña entre todos los conjuntos dominantes de $G$. Una cubierta en una gráfica $G$ es un conjunto $T\subseteq V(G)$ tal que cada arista de $G$ es incidente en al menos un vértice de $T$. El número de cubierta de $G$, $\beta(G)$, es la cardinalidad más pequeña entre todas las cubiertas de $G$. Un 2-acoplamiento de una gráfica $G$ es un conjunto $R\subseteq E(G)$ tal que cualesquiera tres aristas de $R$ no son incidentes a un mismo vértice. El número de 2-acoplamiento, $\nu_2(G)$, es la cardinalidad más grande entre todos los 2-acoplamientos de $G$. Se puede probar \begin{center} $\gamma(G)\leq\beta(G)$ y $\lceil \nu_{2}(G)/2\rceil\leq\beta(G)\leq\nu_2(G)-1,$ \end{center} En esta plática presentaré una caracterización de gráficas simples y conexas que cumplen $\beta(G)=\nu_2(G)-1$, $\beta(G)=\lceil \nu_{2}(G)/2\rceil$ y $\gamma(G)=\nu_2(G)-1$.