Un programa para construir jaulas
Rafael Villarroel Flores (UAEH) 8 de noviembre
Cuándo |
08/11/2011 de 16:30 a 17:30 |
---|---|
Dónde | Salón de seminarios Graciela Salicrup |
Agregar evento al calendario |
vCal iCal |
Decimos que una gráfica simple $G$ es $k$-regular si todo vértice es adyacente
a otros k-vértices. El cuello de $G$ es la longitud del ciclo más
pequeño en $G$. Una $(k,g)$-gráfica es una gráfica k-regular con cuello $g$. Una
$(k,g)$-jaula es una $(k,g)$-gráfica con la menor cantidad de vértices
posible.
La idea de la plática es exponer primero la teoría básica de
las jaulas junto con ejemplos. También se mostrará una
implementación, en el lenguaje Python, de ideas planteadas
por McKay y otros en un artículo reciente, para
buscar $(k,g)$-gráficas de un tamaño dado, y que pudieran aplicarse a
buscar jaulas y en otros problemas en teoría de gráficas.