Un programa para construir jaulas
Rafael Villarroel Flores (UAEH) 8 de noviembre
When |
Nov 08, 2011
from 04:30 PM to 05:30 PM |
---|---|
Where | Salón de seminarios Graciela Salicrup |
Add event to calendar |
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.