Nuevos grafos regulares pequeños de girth dado: el problema de la jaula y más allá

Información Básica

• ID del Artículo: 2511.07247
• Título: New small regular graphs of given girth: the cage problem and beyond
• Autores: Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken, Louis Stubbe, Tibo Van den Eede
• Clasificación: math.CO (Matemática Combinatoria), cs.DM (Matemática Discreta)
• Fecha de Publicación: 11 de noviembre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2511.07247

Resumen

El problema de la jaula (cage problem) se ocupa de encontrar grafos $(k,g)$ con el número mínimo de vértices, es decir, grafos $k$-regulares con girth (circunferencia) $g$. El objetivo central es determinar $n(k,g)$ (el orden mínimo de tales grafos) e identificar los grafos extremales correspondientes. Este artículo estudia el problema de la jaula y sus múltiples variantes desde una perspectiva computacional, desarrollando cuatro algoritmos complementarios de generación de grafos: generación exhaustiva basada en elevaciones (lifts), búsqueda tabú heurística, búsqueda de escalada y técnicas de corte. Utilizando estos métodos, se establecen nuevas cotas superiores para once casos del problema clásico de la jaula: $n(3,16) \leq 936$, $n(3,17) \leq 2048$, $n(4,9) \leq 270$, $n(4,10) \leq 320$, $n(4,11) \leq 713$, $n(5,9) \leq 1116$, $n(6,11) \leq 7783$, $n(8,7) \leq 774$, $n(10,7) \leq 1608$, $n(12,7) \leq 2890$, $n(14,7) \leq 4716$. Estos resultados mejoran múltiples cotas que se mantenían sin cambios durante 22 años, en particular $n(4,10)$ se reduce de 384 a 320, lo que constituye una mejora sustancial.

Antecedentes y Motivación de la Investigación

Definición del Problema

1. Problema Central: El problema de la jaula busca una jaula $(k,g)$ (cage), es decir, un grafo $k$-regular con el número mínimo de vértices $n(k,g)$ y girth $g$. El girth es la longitud del ciclo más corto en el grafo.
2. Importancia del Problema:
   • Significado Teórico: Las jaulas son objetos centrales de estudio en teoría de grafos extremal, estrechamente relacionadas con teorías clásicas como la cota de Moore
   • Aplicaciones Prácticas: Sus estructuras dispersas y altamente simétricas tienen valor en diseño de redes de comunicación, códigos correctores de errores, criptografía y otros campos
   • Diseño de Redes: Proporcionan topologías que soportan propagación eficiente y uniforme de información, evitan sobrecarga de nodos centrales y son robustas ante fallos
3. Limitaciones de Métodos Existentes:
   • Para la mayoría de pares de parámetros $(k,g)$, el valor exacto $n(k,g)$ es desconocido
   • Las cotas existentes no han sido mejoradas durante muchos años (algunas permanecen sin cambios durante 22 años)
   • Los grafos de Moore solo pueden existir cuando $g \in \{3,4,5,6,8,12\}$
   • La complejidad computacional aumenta drásticamente con $k$ y $g$
4. Motivación de la Investigación:
   • Aprovechar la capacidad computacional moderna y algoritmos de optimización para mejorar cotas de larga data
   • Desarrollar métodos computacionales sistemáticos para abordar el problema de la jaula y sus variantes
   • Proporcionar evidencia para investigación teórica mediante construcción de instancias concretas de grafos (como la conjetura de bipartición para jaulas de girth par)

Contribuciones Principales

1. Marco Algorítmico: Se desarrollan cuatro algoritmos complementarios de generación de grafos
   • Algoritmo de retroceso basado en elevaciones de grafos de voltaje (BTA)
   • Búsqueda tabú heurística (TS)
   • Búsqueda de escalada heurística
   • Técnicas de corte
2. Avances en el Problema Clásico de la Jaula: Se establecen once nuevas cotas superiores, incluyendo:
   • $n(4,10) \leq 320$ (reducción significativa desde 384)
   • $n(3,16) \leq 936$ (mejora desde 960)
   • $n(3,17) \leq 2048$ (mejora desde 2176)
   • Primeras cotas no triviales para $n(4,11)$ y $n(6,11)$
3. Progreso en Problemas Variantes:
   • Grafos regulares de girth de arista (egr): 21 nuevas cotas (2 cotas ajustadas)
   • Grafos regulares de girth de vértice (vgr): 29 nuevas cotas (7 cotas ajustadas)
   • Grafos $(k,g,g+1)$: 6 nuevas cotas
   • Espectro $(k,g)$: Se determinan 34 órdenes previamente no resueltos
4. Recursos Computacionales y Reproducibilidad:
   • Aproximadamente 5 años de CPU de trabajo computacional
   • Todo el código y datos disponibles públicamente en GitHub
   • Verificación completa y comprobaciones de integridad

Explicación Detallada de Métodos

Definición de la Tarea

Entrada: Grado regular $k$, girth $g$, restricciones adicionales opcionales (como regularidad de girth de vértice/arista)

Salida: Grafo de orden mínimo que satisface las condiciones, o cota superior mejorada $n(k,g)$

Restricciones: El grafo debe ser $k$-regular (cada vértice tiene grado $k$) y tener girth al menos $g$ (longitud del ciclo más corto $\geq g$)

Técnica Central: Elevaciones de Grafos de Voltaje (Voltage Graph Lifts)

Principios Básicos

Dado un grafo base $G=(V,E)$, un grupo $\Gamma$ y una asignación de voltaje $\alpha: A \rightarrow \Gamma$ (donde $A$ es el conjunto de arcos dirigidos), el grafo elevado $G_\alpha$ tiene conjunto de vértices: $V(G_\alpha) = \{u_s | u \in V, s \in \Gamma\}$

Para cada arco $(u,v) \in A$ y cada $s \in \Gamma$, existe un arco $(u_s, v_{s \cdot \alpha(a)}) \in A(G_\alpha)$.

Propiedades Clave

1. Preservación de Regularidad (Observación 1): $G$ es $k$-regular si y solo si $G_\alpha$ es $k$-regular
2. Condición Necesaria de Conectividad (Observación 2): Si $G$ no es conexo, entonces $G_\alpha$ no es conexo
3. Cálculo de Girth (Proposición 1): El girth de $G_\alpha$ es igual a la longitud del camino cerrado no invertido más corto en el grafo dirigido de $G$ (con voltaje neto $0_\Gamma$)
4. Simplificación del Árbol Generador (Proposición 2): Se pueden asignar todos los voltajes en un árbol generador a $0_\Gamma$ sin cambiar la clase de isomorfismo del grafo elevado

Algoritmo 1: Algoritmo de Retroceso (BTA)

Reglas de Exclusión Estructuradas

Exclusión Basada en Estructura (independiente de la asignación de voltaje):

1. Restricción de Semiaristas: Las semiaristas correspondientes a arcos solo pueden asignarse elementos del grupo de orden 2
2. Optimización del Árbol Generador: Seleccionar un árbol generador $T$, asignar sus aristas voltaje $0_\Gamma$
3. Exclusión Basada en Ciclos: Para aristas no arbóreas, si asignar voltaje $a$ produce un ciclo de longitud $(q+1)s$ (donde $a^s=0_\Gamma$) menor que el girth objetivo, excluir ese voltaje

Exclusión Basada en Asignación (dependiente de asignación parcial de voltaje):

1. Verificación de Canonicidad (Algoritmo 1):
   • Utilizar automorfismos del grupo $\phi_\Gamma$ y automorfismos de aristas $\phi_G$
   • Mantener solo el representante lexicográficamente mínimo
   • Si una asignación parcial no es canónica, todos sus completamientos pueden excluirse
2. Verificación Incremental de Girth (Algoritmo 2):
   • Verificar solo caminos cerrados no invertidos que utilizan la arista recién asignada
   • Explotar la propiedad incremental para mejorar eficiencia

Flujo del Algoritmo (Algoritmo 3)

BTA(G, Γ, g_min):
  1. Ejecutar verificaciones estructurales, determinar conjuntos de voltajes viables N
  2. Asignación recursiva de voltajes:
     - Para cada arco útil d, intentar cada voltaje en N(d)
     - Aplicar verificaciones de girth y canonicidad
     - Si se aprueba, procesar recursivamente el siguiente arco
     - Retroceder al restaurar estado
  3. Tras asignación completa, construir grafo elevado y filtrar

Algoritmo 2: Búsqueda Tabú (TS)

Motivación

BTA tiene alto costo computacional para instancias grandes; TS explora mediante muestreo heurístico asignaciones de voltaje prometedoras.

Componentes Clave

Definición de Vecindario: Todos los completamientos alternativos que cambian exactamente el elemento del grupo correspondiente a una arista

Función de Costo:

1. Basada en Girth ($c_{girth}$): $c_{girth} = \sum_{i=1}^m f(q_i, a_i), \quad f(q,a) = \begin{cases} \frac{1}{q \cdot \text{Ord}(a)} & \text{si } \text{Ord}(a) \neq 1 \\ C & \text{en otro caso} \end{cases}$ donde $C$ es una constante de penalización grande, $m$ es el número de caminos muestreados
2. Basada en Regularidad ($c_{reg}$): $c_{reg} = \min\left[\text{Var}(f_V), \text{Var}(f_D)\right]$ donde $f_V$ y $f_D$ son las frecuencias de aparición de vértices y arcos en ciclos de girth

Lista Tabú: Almacena operaciones de modificación recientes para prevenir retorno inmediato, longitud $3|\Gamma|$

Mecanismo de Perturbación: Cuando se atasca en óptimo local, aplicar modificaciones aleatorias para escapar

Configuración de Hiperparámetros (Tabla 1)

• Límite de cantidad de automorfismos de arista/grupo: 200/2000
• Límite de tiempo BTA y TS: 20 segundos cada uno/instancia
• Girth mínimo del vecindario: $g_{nbr} = g_{min} - 2$ (problema de jaula) o $g_{nbr} = g_{min}$ (problema de regularidad)

Algoritmo 3: Búsqueda de Escalada Heurística

Diferencia con Métodos Anteriores: Busca simultáneamente el grafo base y la asignación de voltaje

Procedimiento:

1. Comenzar con $n$ vértices aislados
2. En cada iteración:
   • Considerar todos los pares de arcos que pueden agregarse y asignaciones de voltaje $t \in T(G)$
   • Seleccionar la modificación que maximiza $|T(G_t)|$ (estrategia greedy)
3. Verificar si el grafo elevado rompe el récord

Algoritmo 4: Técnicas de Corte

Idea Básica: Eliminar vértices de grafos $(k,g+1)$ pequeños conocidos, luego agregar aristas para completar a grafo $k$-regular

Estrategias Específicas:

1. Girth 7, Grado Par $8 \leq k \leq 14$:
   • Eliminar dos vértices $u,v$ a distancia 4 de una jaula $(k,8)$
   • Eliminar $N_1(u), N_1(v), N_2(u,v)$
   • Tamaño del conjunto de corte: $3k$ (mejora sobre $3k-1$ de de Ruiter y Biggs)
2. Girth 11:
   • Desde jaula $(4,12)$: eliminar $u,v$ a distancia 6, $N_1(u), N_1(v), N_3(u,v)$ y un vértice en $N_2(u) \cap N_4(v)$, corte de $3k+3$ vértices
   • Desde jaula $(6,12)$: estrategia similar, corte de $5k-1$ vértices

Configuración Experimental

Recursos Computacionales

• Cómputo Total: Aproximadamente 5 años de CPU
• Infraestructura: Flemish Supercomputer Center (VSC)
• Lenguaje de Implementación: Basado en C++ (inferido, no explícitamente indicado)

Generación de Grafos Base y Grupos

1. Grupos: Usar sistema GAP para generar todos los grupos no isomorfos de orden $n < 1024$
2. Grafos Base:
   • Generador multigraph extendido (multigraph+)
   • Generar grafos regulares conexos que contengan aristas paralelas, bucles y semiaristas
   • Usar Nauty para eliminar grafos isomorfos

Estrategia de Verificación

1. Verificación de Entrada:
   • Grupos: Obtenidos directamente de GAP
   • Grafos Base: Comparar con generador pregraph (hasta orden 13)
2. Corrección de Optimización:
   • Deshabilitar cada optimización independientemente (automorfismos de grafo, automorfismos de grupo, cotas de girth)
   • Verificar que la cantidad de grafos elevados no isomorfos sea consistente
3. Verificación de Exhaustividad:
   • Comparar con tres implementaciones independientes:
     • Construcción basada en $K_{1,3}$
     • Elevaciones de grafos Gray y Theta
     • Generador de grafos cíclicos por bloques (equivalente a elevaciones de grupo cíclico)
   • Salida completamente consistente en todos los casos

Proceso de Filtrado

1. Verificación de Conectividad
2. Filtrado de Isomorfismo: Usar Nauty para construir representación canónica
3. Verificación de Girth y Regularidad: Usar algoritmo de 29

Resultados Experimentales

Resultados Principales: Problema Clásico de la Jaula (Tabla 2)

Mejoras Significativas

Resultados de Técnicas de Corte

• $(8,7) \leq 774$ (mejora de 3 vértices desde 777)
• $(10,7) \leq 1608$ (mejora de 3 vértices desde 1611)
• $(12,7) \leq 2890$ (mejora de 3 vértices desde 2893)
• $(14,7) \leq 4716$ (mejora de 3 vértices desde 4719)

Hallazgos Clave

1. Avance en $(4,10)$: Reducción de 384 a 320, disminución del 16.7%, es la mejora más sorprendente
2. Evidencia de Bipartición: Los nuevos grafos $(3,16)$ y $(4,10)$ son ambos bipartitos, apoyando la conjetura de que "las jaulas de girth par deben ser bipartitas"
3. Detalles de Construcción (Figura 4):
   • $(3,16)$: Usar grupo $C_{13} \rtimes C_9$ (orden 117), grafo base de 8 vértices
   • $(4,10)$: Usar grupo $C_5 \times D_4$ (orden 40), grafo base de 8 vértices

Resultados de Problemas Variantes

Grafos Regulares de Girth de Arista (Tabla 3)

• 21 nuevas cotas, de las cuales 2 cotas ajustadas (límite superior e inferior iguales):
  • $n(4,5,4) = 30$ (recién determinado)
  • Múltiples casos $(6,5,\lambda_e)$ obtienen cotas superiores por primera vez

Grafos Regulares de Girth de Vértice (Tabla 4)

• 29 nuevas cotas, de las cuales 7 cotas ajustadas:
  • $n(3,7,1) = n(3,7,2) = n(3,7,4) = 42$
  • $n(4,5,1) = n(4,5,6) = n(4,5,7) = 30$
  • Mejoras significativas en múltiples casos $(4,6,\lambda_v)$

Espectro $(k,g)$ (Tabla 5)

• Determinar 34 órdenes previamente no resueltos
• Principalmente concentrados en:
  • $(3,11)$ y $(3,12)$: 7 nuevos órdenes
  • $(4,7)$ y $(4,8)$: 12 nuevos órdenes
  • $(5,7)$: 24 nuevos órdenes (desde 184 hasta 256)

Grafos sin Ciclos $(g+1)$ (Tabla 6)

• 6 nuevas cotas:
  • $n(3,11,12) \leq 228$ (mejora desde 272)
  • $n(3,13,14) \leq 600$ (mejora desde 800)
  • $n(3,15,16) \leq 1760$ (mejora desde 2162)

Análisis de Eficiencia de Algoritmos

Estrategia de Asignación de Tiempo

• Por cada combinación grafo base-grupo: BTA 20 segundos, TS 20 segundos
• Búsqueda de solución inicial TS: 2 segundos
• Búsqueda de automorfismo de grafo: 2 segundos

Complementariedad de Algoritmos

1. BTA: Enumeración exhaustiva para instancias pequeñas, garantiza completitud
2. TS: Muestreo heurístico para instancias grandes, buena escalabilidad
3. Escalada: Optimización simultánea de grafo base y asignación, alta flexibilidad
4. Corte: Aprovecha grafos grandes conocidos, fuerte especificidad

Trabajo Relacionado

Investigación del Problema Clásico de la Jaula

1. Cotas Teóricas:
   • Cota de Moore (1963): Cota inferior fundamental
   • Sauer (1967): Desigualdad $n(k,g) < n(k,g+1)$
   • Wong (1982): Encuesta sobre jaulas
2. Métodos de Construcción:
   • Balaban (1972-1973): Jaulas $(3,10)$ y $(3,11)$
   • Benson (1966): Jaulas $(k,12)$
   • Serie de trabajos de Biggs: Múltiples grafos de girth pequeño
3. Métodos Computacionales:
   • McKay et al. (1998): Retroceso rápido para jaulas
   • Exoo (2002-2020): Técnicas de grafos de voltaje
   • de Ruiter & Biggs (2015): Programación entera y corte

Teoría de Elevaciones

• Gross & Tucker (1987): Fundamentos de teoría de grafos topológica
• Exoo & Jajcay (2011): Teoría de girth para elevaciones de grafos de voltaje
• Este artículo: Extensión con métodos de optimización y heurísticas sistemáticas

Problemas Variantes

1. Grafos Regulares de Girth:
   • Jajcay et al. (2018): Grafos regulares de girth de arista
   • Jajcay et al. (2024): Grafos regulares de girth de vértice
   • Goedgebeur & Jooken (2025): Generación exhaustiva
2. Problema de Espectro:
   • Eze et al. (2025): Teoría y métodos computacionales para espectro $(k,g)$
3. Grafos sin Ciclos Cortos:
   • Eze et al. (2026): Grafos $(k,g,g+1)$ y su conexión con problema de jaula

Ventajas de Este Artículo

1. Marco Sistemático: Tratamiento unificado del problema de jaula y múltiples variantes
2. Complementariedad de Algoritmos: Cuatro métodos cubren diferentes escalas y características
3. Mejoras Sustanciales: Rompen múltiples récords de larga data
4. Recursos Abiertos: Código y datos completamente públicos

Conclusiones y Discusión

Conclusiones Principales

1. Avances en Problema Clásico de Jaula:
   • 11 nuevas cotas superiores, con $(4,10)$ mostrando la mejora más significativa (384→320)
   • Algunas cotas permanecen sin cambios durante 22 años, ahora mejoradas por primera vez
   • Primeras cotas no triviales para $(4,11)$ y $(6,11)$
2. Progreso en Problemas Variantes:
   • Grafos regulares de girth de arista/vértice: 50 nuevas cotas (9 cotas ajustadas)
   • Espectro $(k,g)$: 34 órdenes recién determinados
   • Grafos sin ciclos $(g+1)$: 6 cotas mejoradas
3. Contribuciones Metodológicas:
   • Marco algorítmico sistemático basado en elevaciones
   • Reglas de exclusión estructuradas y basadas en asignación
   • Combinación efectiva de métodos heurísticos y exhaustivos

Limitaciones

1. Complejidad Computacional:
   • Parámetros grandes $(k,g)$ aún difíciles de manejar
   • Requiere recursos computacionales significativos (5 años de CPU)
   • Métodos heurísticos no garantizan encontrar solución óptima
2. Rango de Aplicabilidad de Métodos:
   • Método de elevación depende de existencia de grafos base y grupos adecuados
   • Técnica de corte requiere grafo grande conocido como punto de partida
   • Ciertos pares de parámetros no muestran mejora (como $(3,9)$, $(4,7)$ con jaulas conocidas)
3. Brechas Teóricas:
   • En muchos casos, la brecha entre cotas superior e inferior sigue siendo grande
   • No se proporcionan mejoras de cota inferior nueva
   • Para ciertos parámetros, cota superior aún marcada como "?" (desconocida)
4. Sensibilidad de Hiperparámetros:
   • Límites de tiempo, tamaño de lista tabú, etc. requieren ajuste empírico
   • Falta investigación sistemática de optimización de hiperparámetros

Direcciones Futuras

1. Dirección Teórica:
   • Derivar familias infinitas de nuevas construcciones de grafos
   • Mejorar cota de Moore y sus variantes
   • Probar o refutar conjetura de bipartición para jaulas de girth par
2. Mejora de Algoritmos:
   • Desarrollar algoritmos más eficientes para cálculo de girth
   • Explorar diseño heurístico asistido por aprendizaje automático
   • Paralelizar algoritmos para aprovechar arquitecturas multicore modernas
3. Generalización de Técnicas de Corte:
   • Sistematizar estrategia de selección de conjunto de corte
   • Generalizar a más pares de parámetros $(k,g)$
   • Análisis teórico de efectividad de método de corte
4. Exploración de Aplicaciones:
   • Aplicar grafos recién descubiertos a diseño de redes
   • Explorar aplicaciones en códigos correctores de errores
   • Investigar propiedades criptográficas relevantes

Evaluación Profunda

Fortalezas

1. Contribución Empírica Significativa:
   • Romper múltiples récords mantenidos durante 22 años, especialmente mejora significativa en $(4,10)$
   • Proporcionar múltiples construcciones concretas, ofreciendo material para investigación teórica
   • Proporcionar cotas no triviales por primera vez para ciertos parámetros
2. Innovación Metodológica:
   • Reglas de Exclusión Sistemáticas: Exclusión estructurada y basada en asignación reduce significativamente espacio de búsqueda
   • Complementariedad de Algoritmos: BTA, TS, escalada y corte cubren diferentes escenarios
   • Verificación Incremental: Verificación incremental de girth en Algoritmo 2 mejora eficiencia
   • Verificación de Canonicidad: Utilizar simetría para evitar cálculos redundantes
3. Diseño Experimental Riguroso:
   • Estrategia de verificación multinivel (entrada, optimización, exhaustividad)
   • Comparación con tres implementaciones independientes
   • Descripción detallada de configuración de hiperparámetros
   • Soporte completo para reproducibilidad
4. Amplitud de Investigación:
   • No solo enfocarse en problema clásico, sino investigar sistemáticamente cuatro variantes
   • Establecer primeras cotas para múltiples variantes
   • Marco unificado para diferentes problemas
5. Práctica de Ciencia Abierta:
   • Código y datos completamente públicos (GitHub)
   • Grafos incluidos en base de datos House of Graphs
   • Proporcionar certificados verificables (grafos construidos)

Insuficiencias

1. Profundidad Teórica Limitada:
   • Principalmente trabajo computacional/empírico, carece de perspectivas teóricas profundas
   • No proporciona mejoras de cota inferior nueva o análisis teórico
   • Falta explicación teórica de por qué ciertas mejoras de parámetros son significativas
2. Completitud de Métodos:
   • Métodos heurísticos (TS, escalada) sin garantías de completitud
   • Selección de hiperparámetros depende de experiencia, falta investigación sistemática
   • No analizar garantías teóricas o convergencia de diferentes algoritmos
3. Detalles de Reporte Experimental:
   • No reportar contribución específica de cada algoritmo a diferentes mejoras
   • Falta análisis detallado de tiempo de ejecución
   • Falta discusión de casos de fallo o instancias difíciles
4. Problemas de Escalabilidad:
   • Viabilidad de método para $k$ y $g$ más grandes no clara
   • Regularidad de crecimiento de requisitos de recursos computacionales con parámetros no analizada
   • Ciertos resultados marcados "≥100" indican exploración incompleta
5. Organización de Escritura:
   • Detalles técnicos densos, desafío de legibilidad para no especialistas
   • Algunas descripciones de algoritmos incompletas (falta pseudocódigo para Algoritmo 4)
   • Múltiples tablas de resultados pero falta análisis de resumen unificado

Impacto

1. Impacto Académico:
   • Alto: Problema de jaula es problema clásico en teoría de grafos extremal, mejora de récords de larga data tiene importancia significativa
   • Proporcionar vía indirecta de investigación para problemas abiertos famosos como grafo de Moore 57
   • Métodos generalizables a otros problemas de grafos extremales
2. Valor Práctico:
   • Moderado: Nuevos grafos aplicables a diseño de topología de red, códigos correctores de errores
   • Herramientas de código abierto disponibles para otros investigadores
   • Marco algorítmico aplicable a problemas relacionados de optimización combinatoria
3. Reproducibilidad:
   • Excelente: Código y datos completos públicos
   • Estrategia de verificación detallada aumenta confiabilidad
   • Construcciones concretas verificables independientemente
4. Potencial de Investigación Posterior:
   • Nuevas construcciones pueden inspirar descubrimiento de familias infinitas
   • Marco algorítmico aplicable a otros problemas de generación de grafos
   • Resultados de variantes abren nuevas direcciones de investigación

Escenarios de Aplicación

1. Aplicación Directa:
   • Diseño de red que requiere grafos regulares pequeños de girth alto
   • Construcción de códigos LDPC y otros códigos correctores de errores
   • Aplicaciones criptográficas como compartición de claves
2. Herramienta de Investigación:
   • Experimentos computacionales en teoría de grafos extremal
   • Prueba de algoritmos de isomorfismo de grafos y canonicalización
   • Prueba de referencia para heurísticas de optimización combinatoria
3. Recurso Educativo:
   • Demostrar aplicación de métodos computacionales en matemática pura
   • Estudio de caso en diseño y optimización de algoritmos
   • Ejemplo de investigación reproducible y ciencia abierta
4. Campos de Extensión:
   • Otros problemas de grafos extremales (números de Ramsey, problemas de Turán, etc.)
   • Problemas de satisfacción de restricciones
   • Teoría de diseño combinatorio y codificación

Referencias (Seleccionadas)

1. Teoría Fundamental:
   • 45 Sachs (1963): Prueba de existencia de grafos $(k,g)$ para todos $k \geq 2, g \geq 3$
   • 31 Gross & Tucker (1987): Teoría de grafos topológica y teoría de elevaciones
   • 47 Wong (1982): Encuesta integral sobre jaulas
2. Métodos Computacionales:
   • 24 Exoo et al. (2011): Determinación computacional de jaulas $(3,11)$ y $(4,7)$
   • 38 McKay et al. (1998): Principios de retroceso rápido
   • 15 de Ruiter & Biggs (2015): Método de programación entera
3. Avances Recientes:
   • 22 Exoo & Jajcay (2011): Teoría de girth para elevaciones de grafos de voltaje
   • 29 Goedgebeur & Jooken (2025): Generación exhaustiva de grafos regulares de girth de arista
   • 34 Jajcay et al. (2024): Grafos regulares de girth de vértice
4. Herramientas:
   • 37 McKay & Piperno (2014): Software de isomorfismo de grafos Nauty
   • 27 Sistema GAP: Computación en teoría de grupos
   • 12 House of Graphs: Base de datos de grafos

Evaluación General: Este es un artículo de alta calidad en matemática combinatoria computacional que, mediante desarrollo sistemático de algoritmos y experimentos computacionales a gran escala, logra progreso empírico significativo en el problema clásico de jaula y sus variantes. Las innovaciones metodológicas (especialmente reglas de exclusión sistemáticas y complementariedad de algoritmos) y la estrategia rigurosa de verificación son puntos destacados principales. Aunque la profundidad teórica es limitada, sus contribuciones empíricas, práctica de ciencia abierta e impulso al campo lo convierten en una contribución importante. Para investigadores en teoría de grafos extremal, algoritmos de grafos u optimización combinatoria, este artículo proporciona métodos y recursos valiosos.