On Extremal Family Trees $(\mathcal{T}_n)_{n\geqslant 3}$ Beyond Caterpillars and Greedy Constructions

Resumen Técnico: Sobre Familias de Árboles Extremales Más Allá de los Caterpillars y las Construcciones Greedy

Planteamiento del Problema
Este artículo investiga las propiedades extremales del índice Sigma ($\sigma$), una medida cuadrática de la irregularidad de un grafo, sobre la familia $\mathcal{T}_n$ de todos los árboles con $n \geq 3$ vértices. El índice Sigma se define como $\sigma(G) = \sum_{uv \in E(G)} (d_G(u) - d_G(v))^2$. El desafío central abordado es establecer límites precisos para $\sigma$ y comprender qué clases estructurales de árboles alcanzan estos límites. Específicamente, los autores comparan el mínimo global de $\sigma$ sobre todos los árboles frente a los mínimos alcanzados dentro de subclases restringidas, a saber, los árboles caterpillar (oruga) y los árboles greedy (voraces; árboles construidos conectando vértices para minimizar las disparidades de grado localmente). El estudio también busca determinar si los árboles que no son ni caterpillars ni greedy pueden alcanzar valores de $\sigma$ estrictamente entre el mínimo global y el mínimo encontrado en los árboles caterpillar.

Metodología
Los autores emplean una combinación de teoría de grafos estructural y optimización combinatoria:

1. Definiciones y Preliminares: El artículo establece las definiciones de árboles caterpillar (árboles donde la eliminación de las hojas deja un camino) y árboles greedy (construidos conectando iterativamente un nuevo vértice al vértice existente con el grado actual más pequeño que aún no ha alcanzado su grado objetivo).
2. Argumentos de Transformación: Para probar las propiedades extremales, los autores utilizan operaciones de intercambio de aristas. Demuestran que para cualquier árbol no-greedy, un intercambio de arista específico (reconectando vértices para respetar el orden de los grados) disminuye estrictamente el índice Sigma, probando así que el árbol greedy minimiza $\sigma$ para una secuencia de grados fija.
3. Análisis de Casos e Inducción: El artículo analiza estructuras de árboles específicas definidas por el "Problema 1" y el "Problema 2". Estos problemas definen árboles con una espina central y múltiples niveles de vértices colgantes con restricciones de grado específicas (por ejemplo, colgantes de primer nivel con grado $1+r$, de segundo nivel con $1+s$, etc.).
4. Derivación de Fórmulas: Al particionar las aristas basadas en los niveles del árbol (espina-a-nivel 1, nivel 1-a-nivel 2, etc.), los autores derivan fórmulas algebraicas exactas para $\sigma(T)$ para estas familias estructuradas. También analizan el ordenamiento de las secuencias de grados para determinar los valores máximo y mínimo de $\sigma$ para los árboles caterpillar.

Contribuciones Clave y Resultados

• Propiedades Extremales de los Árboles Greedy: El artículo demuestra que, para cualquier secuencia de grados gráfica $D$, el árbol greedy $T_D$ minimiza el índice Sigma entre todos los árboles que realizan $D$.
• Limitaciones de los Árboles Caterpillar: Los autores demuestran que los árboles caterpillar no alcanzan el mínimo global de $\sigma$ sobre toda la familia $\mathcal{T}_n$.
• Existencia de Árboles Extremales Intermedios: Un hallazgo significativo es la prueba de que existen árboles que no son ni caterpillars ni greedy que poseen valores de $\sigma$ estrictamente entre el mínimo global y el valor mínimo alcanzado por los árboles caterpillar. Esto establece un intervalo abierto no vacío que separa el mínimo global del mínimo del caterpillar.
• Fórmulas Exactas para Árboles Estructurados:
  • Lema 3.2 y 3.3: El artículo deriva fórmulas explícitas para el índice Sigma de árboles con tres niveles de colgantes bajo diversas condiciones de grado (crecimiento de grado lineal vs. cuadrático).
  • Teorema 3.6: Se proporciona una fórmula general para árboles con $n$ vértices de espina y $k$ niveles de colgantes, contabilizando el producto de los factores de ramificación y las diferencias de grado al cuadrado entre niveles.
  • Proposición 3.3: Se proporciona una fórmula exacta para el índice Sigma de un árbol caterpillar $C(n, m)$, distinguiendo los casos donde $n=2$ y $n>2$.
• Límites: El artículo presenta límites superiores para el índice Sigma de los árboles caterpillar involucrando el grado promedio y las sumas de las diferencias de grados al cuadrado (Teorema 3.7).

Significancia
El artículo afirma ofrecer nuevas perspectivas sobre el papel de los árboles no-caterpillar y no-greedy en la minimización de invariantes de grafos. Al demostrar que el mínimo global del índice Sigma no se confina a las clases bien estudiadas de árboles caterpillar o greedy, el trabajo resalta las limitaciones estructurales al usar estas clases comunes para problemas extremales. Las fórmulas exactas derivadas y los límites proporcionan un marco analítico unificado para comparar medidas de irregularidad lineales y cuadráticas en árboles. Los autores posicionan estos resultados como una piedra angular fundamental para el estudio de índices topológicos, específicamente para familias de árboles estructuradas, ofreciendo fórmulas precisas validadas en ejemplos de tamaño fijo y secuencias generales.