Generalizações analíticas do espectro de um grafo

Abstract

Neste trabalho, introduzimos os conceitos de p-autovalores e p-autovetores do q-laplaciano de um grafo, que generalizam os conceitos usuais de autovalores e autovetores do laplaciano através do uso de normas associadas aos vértices e às arestas do grafo. Essa abordagem permite reescrever resultados de Teoria dos Grafos em um roupagem analítico-espectral. Estudamos o maior e o segundo menor pautovalores do q-laplaciano, mostrando relações com invariantes como o tamanho de corte máximo e a constante de Cheeger, e apresentamos uma extensão dessa abordagem para a laplaciana sem sinal.

In this work, we introduce the concepts of p-eigenvalues and p-eigenvectors of the q-laplacian of a graph, which generalize the usual concepts of eigenvalues and eigenvectors of the laplacian through the use of norms associated to vertices and edges of the graph. This approach allows the rewriting of graph theory results in analytic-spectral guise. We studied the largest and the second smallest p-eigenvalues of the q-laplacian, showing relationships with invariants such as the maximum cut size and Cheeger constant, and present an extension of this approach for the signless laplacian.