O espectro de grafos threshold e aplicações

Abstract

Nesta tese de doutorado estudamos uma classe de grafos denominada threshold. Iniciamos apresentando algumas caracterizações dos grafos threshold e definindo-os de uma forma apropriada para o nosso propósito. Mais especificamente, estudamos o espectro dos grafos threshold. Para isso apresentamos alguns resultados previamente conhecidos, como por exemplo, em relação à matriz de adjacência, uma redução para o cálculo do polinômio característico e a multiplicidade dos autovalores não principais. Desenvolvemos um algoritmo que constrói uma matriz diagonal D congruente a A + xI , onde A é a matriz de adjacência de um grafo threshold, x é um número real e I é a matriz identidade. Como aplicação, determinamos quantos autovalores de um grafo threshold G pertencem a um intervalo real (a, b]. A implementação do nosso algoritmo depende apenas da sequência binária de um grafo threshold e sua complexidade é de ordem O(n). Tal algoritmo é facilmente adaptado para a matriz distância Θ de um grafo threshold G. Nesta tese apresentamos aplicações desse algoritmo, como a simplicidade dos autovalores principais, a minimalidade do menor autovalor de um threshold, exibindo uma fórmula para esse menor autovalor, uma ordenação dos grafos threshold via índice, e uma classe infinita de grafos threshold com espectro integral. Além disso, apresentamos um novo algoritmo para o cálculo do polinômio característico de um grafo threshold G.

In this thesis we study the class of threshold graphs. We begin showing some characterizations of threshold graphs defining them in a convenient way for our purposes. More specifically, we study the spectrum of threshold graphs. To this end, we show some previously known results about the adjacency matrix, such as the reduction for computing the characteristic polynomial and the multiplicity of non main eigenvalues. We developed an algorithm that constructs a diagonal matrix D con- gruent to A + xI , where A represents the adjacency matrix of a threshold graph and x is a real number. As an application, we determine how many eigenvalues of a threshold graph lie in an interval (a, b]. The algorithm implementation depends only on the binary sequence of the threshold graph, and its complexity is of order O(n). This algorithm is easily adapted for the distance matrix Θ of a threshold graph G. We finish this dissertation showing some applications of this algorithm. We show that the main eigenvalues are simple. We also determine the class of threshold graphs which have the minimum eigenvalue among threshold graphs of order n, and a formula for this eigenvalue is given. We identify an infinite class of threshold graphs with integral spectra. And finally we obtain a simple algorithm to compute the characteristic polynomial of a threshold graph G.