Descubriendo el arcoíris en algunas gráficas de Cayley

Ponente(s): Ricardo Andrés Maass González, Mika Olsen

El concepto de conexidad por trayectorias arcoíris, introducido por Chartrand en 2008, establece que, dada una gráfica conexa y una coloración de sus aristas, debe existir al menos una trayectoria entre cualquier par de vértices en la que no se repita ningún color. Este concepto tiene aplicaciones en seguridad cibernética al modelar rutas seguras de comunicación con el menor número de contraseñas, especialmente tras los atentados del 11-S. Determinar el mínimo número de colores necesarios (llamado conexidad arcoíris, rc(G)) es un problema difícil: se ha probado que calcularlo es NP-completo incluso para rc(G) = 2. En esta plática presentamos resultados sobre la conexidad arcoíris en gráficas de Cayley con r saltos consecutivos y con saltos uno y tres. Aunque estas gráficas han sido ampliamente estudiadas en contextos como redes, criptografía y sistemas paralelos, se desconoce su conexidad arcoíris. Encontrar la conexidad arcoíris en estas gráficas permiten diseñar sistemas de comunicación más seguros.