On the number of generalized cospectral mates of graphs

1. Problema Investigado

O artigo aborda um problema fundamental na teoria espectral de grafos: a determinação de quantos grafos não isomórficos podem compartilhar o mesmo espectro generalizado.

• Contexto: Um grafo é dito "determinado pelo seu espectro" (DS) se todos os grafos com o mesmo espectro de adjacência forem isomórficos a ele. Uma extensão mais forte é a "determinação pelo espectro generalizado" (DGS), onde o espectro generalizado é definido pelo par $(Spec(G), Spec(\bar{G}))$, ou seja, o espectro do grafo e o espectro do seu complemento.
• A Questão Quantitativa: Enquanto a literatura anterior focava em identificar se um grafo é DGS (ou seja, se possui zero companheiros cospectrais), este trabalho investiga a questão quantitativa: qual é o número máximo de companheiros cospectrais generalizados não isomórficos que um grafo pode ter?
• Limitação Anterior: Algoritmos existentes para encontrar tais companheiros dependem da fatoração de inteiros grandes, o que é computacionalmente caro. Além disso, limites superiores precisos para o número de companheiros eram desconhecidos para classes amplas de grafos.

2. Metodologia

A abordagem dos autores baseia-se na análise das propriedades aritméticas da Matriz de Passeio (Walk Matrix) e na utilização da Forma Normal de Smith (Smith Normal Form - SNF).

• Matriz de Passeio ($W(G)$): Para um grafo $G$ com $n$ vértices, $W(G) = [e, A(G)e, \dots, A(G)^{n-1}e]$, onde $e$ é o vetor de uns. Grafos com $W(G)$ não singular são chamados de "controláveis".
• Relação Ortogonal: Se dois grafos $G$ e $H$ são cospectrais generalizados, existe uma única matriz ortogonal racional regular $Q$ tal que $Q^T A(G) Q = A(H)$ e $Qe = e$.
• Nível da Matriz ($\ell(Q)$): Define-se o nível de uma matriz racional $Q$ como o menor inteiro positivo $x$ tal que $xQ$ é uma matriz inteira.
• Restrições Aritméticas: Os autores demonstram que a Forma Normal de Smith de $W(G)$ impõe condições de divisibilidade rigorosas sobre o nível $\ell(Q)$ de qualquer matriz de transformação admissível.
• Classe de Grafos $F_n$: Os autores definem uma família específica de grafos controláveis, denotada por $F_n$, cujas matrizes de passeio satisfazem condições específicas nos seus fatores invariantes ($d_{\lceil n/2 \rceil}(W(G)) = 1$ e $d_{n-1}(W(G)) = 2$).

3. Principais Contribuições e Resultados Teóricos

O trabalho estabelece dois teoremas centrais que ligam a estrutura algébrica da matriz de passeio ao número de companheiros cospectrais:

Teorema 1.1: Unicidade pelo Nível

Para qualquer grafo $G$ na família $F_n$, se dois companheiros cospectrais generalizados $H_1$ e $H_2$ forem gerados por matrizes ortogonais $Q_1$ e $Q_2$ com o mesmo nível ($\ell(Q_1) = \ell(Q_2)$), então $H_1$ e $H_2$ são isomórficos.

• Implicação: O nível da matriz de transformação é um invariante que distingue classes de isomorfismo de companheiros cospectrais dentro desta família.

Teorema 1.2: Limite Superior Quantitativo

Seja $G \in F_n$ e seja a fatoração em primos do último fator invariante da matriz de passeio $d_n(W(G)) = \prod_{j=1}^m p_j^{k_j}$. O número máximo de companheiros cospectrais generalizados não isomórficos de $G$ é limitado por:
$$\left( \prod_{j=1}^m k_j \right) - 1$$

• Lógica: O número de níveis admissíveis possíveis para a matriz $Q$ é determinado pelos expoentes dos fatores primos de $d_n(W(G))$. Como o nível 1 corresponde ao próprio grafo (isomorfismo trivial), subtrai-se 1 para contar apenas os companheiros não isomórficos.

4. Análise Numérica e Exemplos

• Exemplo Concreto ($n=10$): Os autores apresentaram um grafo específico em $F_{10}$ onde o último fator invariante é $19350 = 2 \times 3^2 \times 5^2 \times 43$.
  • Cálculo do limite: $(1+1)(2+1)(2+1)(1+1) - 1 = 2 \times 3 \times 3 \times 2 - 1 = 35 - 1 = 34$? Correção baseada no texto: O texto afirma que o limite é 3. Reavaliando a fatoração no texto: $19350 = 2 \times 3^2 \times 5^2 \times 43$. Os expoentes são 1, 2, 2, 1. O produto dos expoentes (não dos expoentes+1, mas sim o número de escolhas de expoentes possíveis para o nível, que são $0$a$k_j-1$) é$1 \times 2 \times 2 \times 1 = 4$. Subtraindo o caso trivial, temos $4-1=3$.
  • O grafo possui exatamente 3 companheiros cospectrais ($H_1, H_2, H_3$), atingindo o limite superior previsto pelo teorema. Os níveis das matrizes de transformação foram encontrados como 3, 5 e 15, confirmando a unicidade por nível.
• Simulações Estatísticas: Em um experimento com 10.000 grafos aleatórios para várias ordens $n$, a proporção de grafos que pertencem à família $F_n$ estabilizou em aproximadamente 39% para $n$ grandes. Isso indica que o limite superior derivado é aplicável a uma fração significativa de grafos aleatórios.

5. Significado e Impacto

• Generalização: O trabalho estende os resultados de unicidade espectral para uma classe muito mais ampla de grafos do que os anteriormente conhecidos como "determinados pelo espectro generalizado".
• Limites Informados: Fornece um limite superior explícito e computacionalmente eficiente (baseado na fatoração de inteiros) para o número de companheiros cospectrais, superando a necessidade de buscas exaustivas ou fatorações complexas de grandes inteiros em algoritmos anteriores.
• Conexão Estrutural: Estabelece uma ligação profunda entre a teoria dos números (Forma Normal de Smith, divisibilidade) e a teoria espectral de grafos, mostrando como propriedades aritméticas da matriz de passeio restringem a estrutura geométrica do grafo.
• Futuro: O artigo sugere que técnicas similares podem ser aplicadas a outras matrizes (como Laplaciano ou Matriz de Distância) e a vetores de controle diferentes, abrindo caminho para novas descobertas sobre a determinação espectral de grafos.

Em resumo, o artigo resolve uma questão quantitativa aberta na teoria espectral, provando que para uma grande classe de grafos, o número de "imitadores" (companheiros cospectrais) é estritamente limitado pela fatoração prima de um único invariante algébrico da matriz de passeio.