En el campo matemático de la teoría de grafos , una jaula es un grafo regular que tiene el menor número posible de vértices para su circunferencia .
Formalmente, un ( r , g ) -grafo se define como un grafo 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 ( r , g ) -jaula es un ( r , g ) -grafo con el menor número posible de vértices, entre todos los ( r , g ) -grafos . Una (3, g ) -jaula se denomina a menudo g -jaula .
Se sabe que existe un ( r , g ) -grafo para cualquier combinación de r ≥ 2 y g ≥ 3. De ello se deduce que existen todas las ( r , g ) -jaulas .
Si existe un grafo de Moore con grado r y circunferencia g , debe ser una jaula. Además, los límites de los tamaños de los grafos de Moore se generalizan a las jaulas: cualquier jaula con circunferencia impar g debe tener al menos
vértices, y cualquier jaula con circunferencia par g debe tener al menos
vértices. Cualquier ( r , g ) -grafo con exactamente esta cantidad de vértices es, por definición, un grafo 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 de Balaban , el grafo de Harries y el grafo de Harries–Wong . Pero solo hay una jaula (3, 11) : la jaula de 11 de Balaban (con 112 vértices).
Un grafo 1-regular no tiene ciclo, y un grafo 2-regular conexo tiene 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 grafo completo K r + 1 en r + 1 vértices, y la jaula ( r ,4) es un grafo 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 estricto o casi estricto (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 exponencialmente pero a una tasa mayor que el límite de Moore). Específicamente, la construcción de grafos de Ramanujan definidos por Lubotzky, Phillips y Sarnak (1988) satisfacen 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.
