Conexidad monocromática en digráficas fuertemente conexas

Ponente(s): Mucuy-kak Guevara Aguirre, Diego González-Moreno, Juan José Montellano

Una coloración de flechas de una digráfica fuertemente conexa $D$ es una coloración monocromática fuertemente conexa si para cada par de vértices $u, v$ en $D$ existe una $(u,v)$- y una $(v,u)$-trayectoria monocromática. Denotamos por $smc(D)$ el número máximo de colores en una coloración monocromática fuertemente conexa de $D$. En esta plática probaremos que si $D$ es una digráfica fuertemente conexa de tamaño $m$, entonces $smc(D)= m-\Omega(D)+1$, donde $\Omega(D)$ es el tamaño mínimo de una subdigráfica generadora fuertemente conexa de $D$. Como corolario de este resultado, se obtiene que una digráfica fuertemente conexa $D$ de orden $n$ es hamiltoniana si y sólo si $smc(D) = m - n +1$.