Jaula (teoría de grafos)

Formalmente, un (r,g)-grafo se define como un grafo en el cual cada vértice tiene exactamente r vecinos, y en el cual el ciclo más corto tiene una longitud exactamente de g. Se sabe que existen (r,g)-grafos para cualquier combinación de r ≥ 2 y g ≥ 3.Si existe un grafo de Moore de grado r y cintura g, debe ser una jaula.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.Las cotas inferiores más conocidas de g son también logarítmicas, pero con un factor constante menor (lo que implica que n crece exponencialmente pero a un ritmo más alto que la cota de Moore).Específicamente, los grafos de Ramanujan (Lubotzky, Phillips y Sarnak, 1988) satisfacen la cota Es poco probable que estos grafos sean en sí mismos jaulas, pero su existencia pone un límite superior para el número de vértices necesarios en una jaula.