Integralidade de grafos

Abstract

A Teoria Espectral de Grafos tem como objetivo descobrir propriedades de um grafo G através da análise do espectro de uma matriz associada ao grafo. Nesta dissertação estudamos a matriz de adjacência A(G), a matriz laplaciana L(G) e a matriz laplaciana sem sinal Q(G). Para cada uma dessas matrizes estudamos o comportamento dos autovalores no que diz respeito `a integralidade. Mais especificamente, estudamos os grafos integrais, os grafos Q-integrais e os grafos L-integrais, que são os grafos que têm espectro inteiro em relação `as matrizes A(G), Q(G) e L(G), respectivamente. Estudamos a variação espectral inteira via adição de aresta para a matriz laplaciana. Vimos que se os autovalores da matriz laplaciana variam de maneira inteira, então um dos autovalores aumenta em duas unidades ou dois dos autovalores aumentam em uma unidade cada um. Esses dois tipos de variações são conhecidas como variação espectral inteira em um lugar e dois lugares [26, 33], respectivamente. Essas duas variações foram cruciais para estabelecermos uma estratégia para construção de grafos L-integrais por adição de arestas. Além disso, estudamos os grafos construtivelmente laplaciano integrais [28], que são um subconjunto dos grafos L-integrais. Caracterizamos este subconjunto através dos subgrafos induzidos e mostramos uma técnica alternativa para calcular o seu espectro. Estudamos também algumas famílias com infinitos grafos integrais e grafos Q-integrais construídos através do join de grafos regulares [12, 15, 24].

The spectral graph theory aims to discover properties of a graph G by analyzing the spectrum of a matrix associated to the graph. In this thesis, we study the adjacency matrix A(G), Laplacian matrix L(G) and the signless Laplacian matrix Q(G). For each of these matrices we study the behavior of eigenvalues with respect to integrality. More specifically, we study integral graphs, Q-integral graphs and L-integral graphs, which are graphs that have integral spectrum with regard to the matrices A(G), Q(G) and L(G), respectively. We study the spectral integral variation for the Laplacian matrix under the addition of an edge. We have seen that if the eigenvalues of the Laplacian matrix change by integer quantities, then one of the eigenvalues increases by two units or two of the eigenvalues increase by one unit each. These two types of variation are known as spectral integral variation in one place and two places [26, 33], respectively. These two variations were crucial to establish a strategy for building L-integral graphs by adding edges. Moreover, we studied the class of constructably Laplacian integral graphs, that are a subset of L-integral graphs. We characterize this subset through vertex-induced subgraphs and show an alternative technique for calculating their spectrum. We also study some families with infinite integral graphs and Q-integral graphs built through the join of regular graphs [12, 15, 24].