Número mínimo de autovalores de grafos unicíclicos

Abstract

Neste trabalho, estudamos o número mínimo de autovalores de grafos unicíclicos. Fizemos uma exposição de resultados clássicos e recentes do Problema Inverso de Autovalor para Grafos (IEP-G). Foi feita uma revisão de literatura com foco em técnicas que têm se mostrado eficientes para resolver problemas relacionados ao IEP-G. Além disso, trazemos algoritmos de diagonalização em grafos com no máximo um ciclo, nos permitindo determinar a multiplicidade de um autovalor em matrizes simétricas associadas a árvores ou grafos unicíclicos. Como contribuições, calculamos o número mínimo de autovalores do grafo (k, ℓ)-sol, para k par, o qual é obtido de um ciclo Ck conectando um único Pℓ a cada vértice do ciclo. Finalmente, derivamos uma nova cota inferior para o caso em que k é ímpar.

In this work, we studied the minimum number of distinct eigenvalues in unicyclic graphs. We did an exhibition of classical and recent results of the Inverse Eigenvalue Problem for Graphs (IEP-G). A literature review was carried out with a focus on techniques that have proven efficient in solving problems related to the IEP-G. Furthermore, we present diagonalization algorithms for graphs with at most one cycle, enabling us to determine the multiplicity of an eigenvalue of symmetric matrices associated with trees and unicyclic graphs. As original contributions, we compute the minimum number of distinct eigenvalues of the (k, ℓ)-sun, when k is even, which is obtained from a cycle CK by attaching a path Pℓ to each cycle vertex. Finally, we derive a new lower bound for the case when k is odd.