Cotas para a soma de autovalores de grafos

Abstract

Neste trabalho, investigamos problemas envolvendo desigualdades para os autovalores das matrizes Laplaciana e Laplaciana sem sinal. Estudamos o problema de Nordhaus-Gaddum e obtemos resultados para os dois maiores autovalores da matriz Laplaciana e para o segundo maior e menor autovalores da matriz Laplaciana sem sinal. Na maioria dos casos, garantimos que as desigualdades obtidas são os melhores possíveis. Apresentamos uma técnica para obter uma cota superior para a soma dos k maiores autovalores da matriz Laplaciana sem sinal de classes de grafos que possuam uma cota superior específica para o maior autovalor dessa matriz. Em 2013, F. Ashraf et al. [7] propuseram uma versão da conjectura de Brouwer para a matriz Laplaciana sem sinal. Essa conjectura foi provada para diversos casos, mas não possui uma demonstração para o caso geral. Investigamos sua validade para os cografos e grafos threshold, apresentando alguns resultados parciais.

In this work, we investigate problems involving inequalities for the eigenvalues of the Laplacian and signless Laplacian matrices. We studied the Nordhaus- Gaddum problem and obtained results for the two largest eigenvalues of the Laplacian matrix and for the second largest and smallest eigenvalues of the signless Laplacian matrix. In most cases, we guarantee that the inequalities obtained are best possible. We present a technique to obtain an upper bound for the sum of the k largest eigenvalues of the signless Laplacian matrix of classes of graphs that have a specific upper bound for the largest eigenvalue of that matrix. In 2013, F. Ashraf et al. [7] proposed a version of Brouwer conjecture for the signless Laplacian matrix. This conjecture has been proved for several cases, but it does not have a proof for the general case. We investigated its validity for cographs and threshold graphs, presenting some partial results.