Jaula (teoría de grafos)

En el área matemática de la teoría de grafos, una jaula es un grafo regular que tiene la menor cantidad de vértices posible para su cintura.

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. Una (r,g)-jaula es un (r,g)-grafo con el menor número de vértices posible, entre todos los (r,g)-grafos.

Si existe un grafo de Moore de grado r y cintura g, debe ser una jaula. Es más, los límites de los tamaños de los grafos de Moore se generalizan a las jaulas: cualquier jaula de cintura impar g debe tener como mínimo

vértices, y cualquier jaula de cintura par g debe tener como mínimo

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 varias jaulas para una combinación dada de r y g. Por ejemplo, hay tres (3,10)-jaulas no isomórficas, cada una con 70 vértices : la 10-jaula de Balaban, el grafo de Harries y el grafo de Harries-Wong. Pero existe solo una (3,11)-jaula : la 11-jaula de Balaban (con 112 vértices).

Un grafo de grado uno no tiene ciclos, y un grafo conexo de grado dos tiene una cintura igual al número de sus vértices, por lo que las jaulas solo son de interés para r ≥ 3. La (r,3)-jaula es un grafo completo K_r+1 sobre r+1 vértices, y la (r,4)-jaula es un grafo bipartito completo K_r,r sobre 2r vértices.

Otras jaulas destacables son los grafos de Moore:

El número de vértices en las (r,g)-jaulas conocidas, para valores de r > 2 y g > 2, aparte de planos proyectivos y polígonos generalizados, es:

Para valores grandes de g, la cota de Moore implica que el número n de vértices debe crecer al menos exponencialmente como función de g. De manera equivalente, g puede ser como máximo proporcional al logaritmo de n. Más precisamente,

Se cree que esta cota es estrecha o está cerca de ser estrecha (Bollobás y Szemerédi, 2002). 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.

---