Decomposição de espectros de grafos e aplicações

Abstract

Neste trabalho, apresentamos um algoritmo que decompõe o espectro de uma matriz associada a um grafo em uma união de espectros de matrizes de ordem menor, se o grafo possui certas simetrias. Este método unifica técnicas usadas por vários autores. Para a execução do algoritmo, são introduzidos os grafos com pesos generalizados (GWG), estruturas que representam matrizes simétricas com componentes reais arbitrárias. Como aplicação direta do algoritmo, obtemos o espectro das matrizes de adjacências, laplaciana, laplaciana sem sinal e laplaciana normalizada de grafos threshold, árvores de Bethe generalizadas e grafos multi-leque. Uma segunda aplicação do algoritmo consiste na análise de uma operação que adiciona arestas em partes simétricas de um grafo de modo que o espectro laplaciano do grafo se mantém controlado. Como consequência, é possível montar uma família, da ordem de n/2 elementos, formada por grafos unicíclicos com n vértices que não são coespectrais, mas que possuem a mesma energia laplaciana. O terceiro problema abordado consiste no ordenamento de árvores de acordo com sua energia laplaciana. Utilizando uma nova cota superior para a soma dos maiores autovalores laplacianos, encontramos o conjunto de f(n) árvores com n vértices com maior energia laplaciana, onde f(n) é aproximadamente p n.

Is this work, we present an algorithm that partitions the spectrum of a matrix associated to a graph into a union of spectra of smaller matrices, provided that the graph has some special symmetries. This method uni es techniques used by several authors. To execute the algorithm, we introduce generalized weighted graphs (GWG), structures that represent symmetric matrices with arbitrary real components. As an application of the algorithm, we obtain the spectrum of the adjacency, Laplacian, signless Laplacian and normalized Laplacian matrices of threshold graphs, generalized Bethe trees and multi-fan graphs. A second application of the algorithm consists of the analysis of an operation that adds edges to symmetric parts of the graph in such a way that the change in the Laplacian spectrum of the graph is controlled. As a consequence, it is possible to build a family of n-vertex noncoespectral unicyclic graphs of cardinality about n/2 , all of them with the same Laplacian energy. The third problem is to order trees with respect to their Laplacian energy. Using a new upper bound on the sum of the largest Laplacian eigenvalues, we are able to nd the family of f(n) trees with n vertices with the largest Laplacian energy, where f(n) is approximately p n.