Construindo Matrizes de Árvores com Multiplicidade Máxima

Resumen

Seja G = (V, E) um grafo simples com conjunto de vértices V = {v₁, ..., v_n} e conjunto de arestas E. Dizemos que uma matriz simétrica A = (a_ij) de ordem n × n é associada ao grafo G se, para todo i ≠ j, a_ij ≠ 0 se e somente se {v_i, v_j} ∈ E. Definimos S(G) como o subconjunto de todas as matrizes simétricas associadas ao grafo G. Denotaremos por Spec(A) o multiconjunto dos autovalores da matriz A. Definimos a multiplicidade máxima de um grafo G como M(G) := max{m_A(λ) : A ∈ S(G), λ ∈ Spec(A)}, onde m_A(λ) denota a multiplicidade de λ como autovalor da matriz A. Este parâmetro está associado a uma classe de problemas em Teoria Matricial Combinatória, denominada Problema Inverso de Autovalor para Grafos (ou IEP-G, do inglês Inverse Eigenvalue Problem for Graphs), que tem recebido atenção de pesquisadores. [...]