jaula

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 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 y el . Pero existe solo una (3,11)-jaula : la (con 112 vértices).