En el campo matemático de la teoría de grafos , una jaula es un gráfico regular que tiene el menor número posible de vértices en su circunferencia .
Formalmente, un gráfico ( r , g ) se define como un gráfico en el que cada vértice tiene exactamente r vecinos y en el que el ciclo más corto tiene una longitud exactamente g . Una jaula ( r , g ) es un gráfico ( r , g ) con el menor número posible de vértices, entre todos los gráficos ( r , g ) . Una jaula (3, g ) a menudo se denomina jaula g .
Se sabe que existe un gráfico ( r , g ) para cualquier combinación de r ≥ 2 y g ≥ 3 . De ello se deduce que todas las ( r , g ) -jaulas existen.
Si existe un gráfico de Moore con grado r y circunferencia g , debe ser una jaula. Además, los límites de los tamaños de los gráficos de Moore se generalizan a las jaulas: cualquier jaula con circunferencia impar g debe tener al menos
vértices, y cualquier jaula con circunferencia uniforme g debe tener al menos
vértices. Cualquier gráfico ( r , g ) con exactamente tantos vértices es, por definición, un gráfico de Moore y, por lo tanto, automáticamente una jaula.
Pueden existir múltiples jaulas para una combinación dada de r y g . Por ejemplo, hay tres jaulas (3, 10) no isomorfas , cada una con 70 vértices: la jaula de 10 Balaban , el gráfico de Harries y el gráfico de Harries-Wong . Pero sólo hay una jaula (3, 11) : la jaula Balaban 11 (con 112 vértices).
Un gráfico 1-regular no tiene ciclo, y un gráfico 2-regular conectado tiene una circunferencia igual a su número de vértices, por lo que las jaulas solo son de interés para r ≥ 3. La jaula ( r ,3) es un gráfico completo K r +1 en r +1 vértices, y la jaula ( r ,4) es un gráfico bipartito completo K r , r en 2 r vértices.
Las jaulas notables incluyen:
Los números de vértices en las jaulas conocidas ( r , g ), para valores de r > 2 y g > 2, distintos de los planos proyectivos y los polígonos generalizados, son:
Para valores grandes de g , el límite de Moore implica que el número n de vértices debe crecer al menos exponencialmente en función de g . De manera equivalente, g puede ser como máximo proporcional al logaritmo de n . Más precisamente,
Se cree que este límite es estrecho o casi estrecho (Bollobás y Szemerédi 2002). Los límites inferiores más conocidos de g también son logarítmicos, pero con un factor constante más pequeño (lo que implica que n crece individualmente exponencialmente pero a una tasa mayor que el límite de Moore). Específicamente, la construcción de gráficos de Ramanujan definidos por Lubotzky, Phillips y Sarnak (1988) satisface el límite
Este límite fue mejorado ligeramente por Lazebnik, Ustimenko y Woldar (1995).
Es poco probable que estos gráficos sean en sí mismos jaulas, pero su existencia da un límite superior al número de vértices necesarios en una jaula.
