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

Resumo Técnico: Sobre Famílias de Árvores Extremais Além de Lagartas e Construções Gananciosas

Enunciado do Problema
Este artigo investiga as propriedades extremais do índice Sigma ($\sigma$), uma medida quadrática de irregularidade de grafos, sobre a família $\mathcal{T}_n$ de todas as árvores com $n \geq 3$ vértices. O índice Sigma é definido como $\sigma(G) = \sum_{uv \in E(G)} (d_G(u) - d_G(v))^2$. O desafio central abordado é estabelecer limites precisos para $\sigma$ e compreender quais classes estruturais de árvores alcançam esses limites. Especificamente, os autores comparam o mínimo global de $\sigma$ sobre todas as árvores contra os mínimos alcançados dentro de subclasses restritas, nomeadamente árvores lagartas (caterpillars) e árvores gananciosas (greedy trees — árvores construídas conectando vértices para minimizar disparidades de grau localmente). O estudo também busca determinar se árvores que não são nem lagartas nem gananciosas podem alcançar valores de $\sigma$ estritamente entre o mínimo global e o mínimo encontrado nas árvores lagartas.

Metodologia
Os autores empregam uma combinação de teoria de grafos estrutural e otimização combinatória:

1. Definições e Preliminares: O artigo estabelece definições para árvores lagartas (árvores onde a remoção das folhas resulta em um caminho) e árvores gananciosas (construídas conectando iterativamente um novo vértice ao vértice existente com o menor grau atual que ainda não atingiu seu grau alvo).
2. Argumentos de Transformação: Para provar propriedades extremais, os autores utilizam operações de troca de arestas (edge-switching). Eles demonstram que, para qualquer árvore não gananciosa, uma troca de aresta específica (reconectando vértices para respeitar a ordenação de graus) diminui estritamente o índice Sigma, provando assim que a árvore gananciosa minimiza $\sigma$ para uma sequência de graus fixa.
3. Análise de Casos e Indução: O artigo analisa estruturas de árvores específicas definidas pelos "Problema 1" e "Problema 2". Esses problemas definem árvores com uma espinha central e múltiplos níveis de vértices pendentes com restrições de grau específicas (ex: pendentes de primeiro nível com grau $1+r$, de segundo nível com $1+s$, etc.).
4. Derivação de Fórmulas: Ao particionar as arestas com base nos níveis da árvore (espinha-para-nível 1, nível 1-para-nível 2, etc.), os autores derivam fórmulas algébricas exatas para $\sigma(T)$ para essas famílias estruturadas. Eles também analisam a ordenação de sequências de graus para determinar os valores máximo e mínimo de $\sigma$ para árvores lagartas.

Principais Contribuições e Resultados

• Propriedades Extremais de Árvores Gananciosas: O artigo prova que, para qualquer sequência de graus gráfica $D$, a árvore gananciosa $T_D$ minimiza o índice Sigma entre todas as árvores que realizam $D$.
• Limitações de Árvores Lagartas: Os autores provam que as árvores lagartas não alcançam o mínimo global de $\sigma$ sobre toda a família $\mathcal{T}_n$.
• Existência de Árvores Extremais Intermediárias: Uma descoberta significativa é a prova de que existem árvores que não são nem lagartas nem gananciosas que possuem valores de $\sigma$ estritamente entre o mínimo global e o valor mínimo alcançado pelas árvores lagartas. Isso estabelece um intervalo aberto não vazio separando o mínimo global do mínimo da lagarta.
• Fórmulas Exatas para Árvores Estruturadas:
  • Lema 3.2 & 3.3: O artigo deriva fórmulas explícitas para o índice Sigma de árvores com três níveis de pendentes sob variadas condições de grau (crescimento de grau linear vs. quadrático).
  • Teorema 3.6: Uma fórmula geral é fornecida para árvores com $n$ vértices da espinha e $k$ níveis de pendentes, contabilizando o produto dos fatores de ramificação e as diferenças de graus ao quadrado entre os níveis.
  • Proposição 3.3: Uma fórmula exata para o índice Sigma de uma árvore lagarta $C(n, m)$ é fornecida, distinguindo casos onde $n=2$ e $n>2$.
• Limites (Bounds): O artigo apresenta limites superiores para o índice Sigma de árvores lagartas envolvendo o grau médio e somas de diferenças de graus ao quadrado (Teorema 3.7).

Significância
O artigo afirma oferecer novos insights sobre o papel de árvores não-lagartas e não-gananciosas na minimização de invariantes de grafos. Ao demonstrar que o mínimo global do índice Sigma não está confinado às classes amplamente estudadas de árvores lagartas ou gananciosas, o trabalho destaca as limitações estruturais no uso dessas classes comuns para problemas extremais. As fórmulas exatas derivadas e os limites fornecem um arcabouço analítico unificado para comparar medidas de irregularidade linear e quadrática em árvores. Os autores posicionam esses resultados como um pilar fundamental para o estudo de índices topológicos, especificamente para famílias estruturadas de árvores, oferecendo fórmulas precisas validadas em exemplos de tamanho fixo e sequências gerais.