Grafos com poucos autovalores distintos

Abstract

Em seu survey [60], Nikiforov propôs dois problemas relacionados à caracterização da igualdade em duas cotas para a energia de um grafo. Mostramos que os grafos desse tipo possuem no máximo dois autovalores não nulos distintos em valor absoluto, logo são grafos com no máximo cinco autovalores distintos. Motivados por essa conexão, apresentamos avanços no compreensão da estrutura de grafos com poucos autovalores distintos. Estudamos os problemas propostos de acordo com o tipo de espectro que esses grafos possam ter e, em muitos desses casos os grafos são caracterizados, em outros apresentamos famílias infinitas de grafos satisfazendo a restrição. Observamos que muitas famílias de grafos que apresentamos são integrais. Inspirados por esse fato, também estudamos grafos integrais com poucos autovalores distintos. Entre nossos resultados, caracterizamos árvores integrais com 5 autovalores distintos.

In his survey [60], Nikiforov proposed two problems related to the characterization of equality in two bounds for the energy of a graph. We show that graphs of this type have at most two distinct non-zero eigenvalues in absolute value, so they are graphs with at most five distinct eigenvalues. Motivated by this connection, we present advances in understanding the structure of graphs with few distinct eigenvalues. We study the proposed problems according to the type of spectrum that these graphs may have and, in many of these cases the graphs are characterized, in others we present infinite families of graphs satisfying the restriction. We observe that many families of graphs we present are integral. Inspired by this fact, we also study integral graphs with few distinct eigenvalues. Among our results, we characterize integral trees with 5 distinct eigenvalues.