Entrelaçamento de Autovalores em Grafos

Abstract

A teoria espectral de grafos visa descobrir propriedades de um grafo G por meio da análise do espectro de uma matriz associada ao grafo. Neste trabalho, estudamos a matriz de adjacência A, a matriz laplaciana L, a matriz laplaciana normalizada L e a matriz laplaciana sem sinal Q e para essas matrizes apresentamos resultados de entrelaçamento de autovalores associados com as operações de deleção de uma aresta e de deleção de um vértice. Além disso, mostramos resultados de entrelaçamento de autovalores associados com a operação de contração de dois vértices para a matriz de adjacência A e para matriz laplaciana normalizada L. Como contribuição original construímos resultados de entrelaçamento de autovalores associados com a operação de subdivisão de uma aresta para as matrizes A, L, L e Q, e associados com a operação de contração de vértices para L e Q.

The spectral graph theory aims to discover properties of a graph G through the analysis of the spectrum of a matrix associated with the graph. In this work, we study the adjacency matrix A, the standard Laplacian matrix L, the normalized Laplacian matrix L and the signless Laplacian matrix Q and for these matrices we present eigenvalues interlacing results associated with the operations of deleting an edge and deleting a vertex. Moreover, we show eigenvalues interlacing results associated with the vertex contraction operation for the adjacency matrix A and the normalized laplacian matrix L. As original contribution, we prove some results about eigenvalues interlacing associated with the operation of subdivision of an edge for the matrices A, L, L and Q, and associated with the vertex contraction operation for L and Q.