Jaula (teoría de grafos)
En el área matemática de la teoría de grafos , una jaula es un gráfico regular que tiene la menor cantidad posible de vértices para 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 una gráfica ( r , g ) con el menor número posible de vértices, entre todas las gráficas ( r , g ). Una jaula (3, g ) a menudo se llama 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 existen todas las jaulas ( r , g ).
Si existe un gráfico de Moore con grado r y circunferencia g , debe ser una jaula. Por otra parte, los límites de los tamaños de los gráficos Moore generalizar a jaulas: cualquier jaula con impar circunferencia g debe tener al menos
vértices. Cualquier gráfico ( r , g ) con exactamente esta cantidad de vértices es, por definición, un gráfico 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 jaulas no isomórficas (3,10), cada una con 70 vértices: la jaula Balaban de 10 , la gráfica de Harries y la gráfica de Harries-Wong . Pero solo hay una jaula ( 3,11): la jaula Balaban de 11 (con 112 vértices).
