Conjeturas sobre jaulas regulares con dos cuellos prefijados

En 1983 Harary y Kovacs propusieron una extensión del problema sobre construcción de jaulas: Construir grafos regulares con el menor número posible de vértices con dos cuellos prefijados con distinta paridad. En el mismo artículo plantearon muchas e interesantes conjeturas sobre estos objetos. En esta charla revisaremos dos: la conjetura de que cualquier jaula con cuello impar g contiene ciclos pares de longitud g + 1, que Harary y Kovacs probaron para (k, 5)-jaulas siempre que 2k − 1 sea potencia de primo. Y la conjetura que establece una cota inferior sobre el orden n(k, h) de cualquier jaula k-regular con cuello h. Concretamente plantearon que n(k, h) ≥ n(k; g, h) donde n(k; g, h) denota el orden de una k-jaula con dos cuellos prefijados de distinta paridad g < h.