Repositório Digital

A- A A+

O espectro de grafos threshold e aplicações

.

O espectro de grafos threshold e aplicações

Mostrar registro completo

Estatísticas

Título O espectro de grafos threshold e aplicações
Autor Tura, Fernando Colman
Orientador Trevisan, Vilmar
Data 2013
Nível Doutorado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Matemática. Programa de Pós-Graduação em Matemática Aplicada.
Assunto Grafos
Resumo 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.
Abstract 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.
Tipo Tese
URI http://hdl.handle.net/10183/77731
Arquivos Descrição Formato
000897221.pdf (1.072Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.