RELAÇÕES DE NORDHAUS-GADDUM PARA OS AUTOVALORES DAS MATRIZES LAPLACIANA E LAPLACIANA SEM SINAL

Abstract

In 1956, Edward A. Nordhaus and Jerry W. Gaddum studied the chromatic number in a graph and in its complement together. Since then, any bound on the sum and/or the product of an invariant in a graph and the same invariant in its complement is called a Nordhaus-Gaddum type relation. In this work, we present a survey of these relations for Laplacian and signless Laplacian eigenvalues. As original contributions, we present partial solutions for two conjectures about the largest Laplacian eigenvalue, we also present a new sharp lower bound and show that it is the best possible. In addition, we establish new Nordhaus-Gaddum sharp upper bounds for the second largest Laplacian eigenvalue and based on this results, we propose a new conjecture to future research.

Em 1956, os pesquisadores Edward A. Nordhaus e Jerry W. Gaddum estudaram o número crom´ atico de um grafo juntamente com o número cromático de seu grafo complementar e obtiveram cotas inferiores e superiores para a soma e o produto deste invariante em função do número de vértices. Desde então, qualquer inequação para a soma ou produto de um invariante de um grafo e o mesmo invariante em seu grafo complementar passou a ser denominada por relação de Nordhaus-Gaddum. Neste trabalho, reunimos todos os resultados existentes na literatura para as relações de Nordhaus- Gaddum envolvendo os autovalores das matrizes laplaciana e laplaciana sem sinal. Como contribuições originais, desenvolvemos soluções parciais para duas conjecturas sobre maior autovalor da matriz laplaciana, apresentamos uma nova cota inferior de Nordhaus-Gaddum para o segundo maior autovalor da matriz laplaciana e provamos que ela é a melhor possível. Além disso, produzimos novas cotas superiores de Nordhaus- Gaddum para este autovalor e com base nestes resultados, propusemos uma conjectura para estudos futuros.