Número mínimo de autovalores distintos de um grafo

Abstract

Este trabalho explora o invariante espectral 𝑞(𝐺), ou seja, o número mínimo de autovalores distintos do grafo (𝐺), em grafos threshold, destacando a conexão entre a estrutura dos grafos e o espectro de matrizes simétricas associadas. Adotamos duas abordagens principais, primeiro estruturamos uma matriz de vértice-clique para demonstrar alguns resultados relacionados com o número mínimo de autovalores distintos de grafos threshold 𝐺 em casos específicos. Em seguida, introduzimos a representação de cografos e bags para, juntamente com o conceito de grafos com pesos e grafos com peso uniforme, podermos aplicar o Algoritmo de Jones et al. [28] no teorema final, obtendo uma nova prova para o mesmo. Este teorema estipula valores para os autovalores de uma família especifica de grafos threshold ao ajustarmos os pesos dos vértices e arestas do grafo 𝐺 conforme definidos. A possibilidade de generalizar essas técnicas para outras classes de grafos reforça o potencial do parâmetro 𝑞(𝐺) na evolução de modelos matemáticos aplicados em diversas ciências. Os resultados obtidos contribuem para o avanço da Teoria Espectral de Grafos, com potencial para impactar diversas áreas e promover novas direções de pesquisa.

This work explores the spectral invariant 𝑞(𝐺), that is, the minimum number of distinct eigenvalues of the graph (𝐺), in threshold graphs, highlighting the connection between the graph structure and the spectrum of associated symmetric matrices. We adopt two main approaches, first we structure a vertex-clique matrix to demonstrate some results related to the minimum number of distinct eigenvalues of threshold graphs 𝐺 in specific cases. Then, we introduce the representation of cographs and bags so that, together with the concept of weighted graphs and uniformly weighted graphs, we can apply the Jones Algorithm et al. [28] in the final theorem, obtaining a new proof for it. This theorem stipulates values for the eigenvalues of a specific family of graphs threshold by adjusting the weights of the vertices and edges of the graph 𝐺 as defined. The possibility of generalizing these techniques to other classes of graphs reinforces the potential of the parameter 𝑞(𝐺) in the evolution of mathematical models applied in several sciences. The results obtained contribute to the advancement of Spectral Graph Theory, with the potential to impact several areas and promote new research directions.