Spectral Invariants associated with Graphs and Mixed Graphs

Abstract

La presente tesis se enmarca dentro de la Teoría Espectral de Grafos. Un grafo es una estructura interconectada conformada por vértices que representan Ítems y lados que representan las relaciones entre los ítems. La Teoría Espectral de Grafos es el estudio del comportamiento de los autovalores de ciertas matrices asociadas a un grafo. Estas matrices pueden ser: la matriz de adyacencia, la matriz Laplaciana y matriz Laplaciana sin signo. Algunas de ellas serán detalladas en el desarrollo de la tesis. Los autovalores de estas matrices se relacionan con parámetros del grafo, entre ellos, número de vértices, número de lados, grado de los vértices, máximo y mínimo grado en vértices, número de lados dirigidos y número de lados no dirigidos (en el caso de grafos mixtos). Similarmente, algunos índices, definidos como funciones de los autovalores de alguna matriz asociada al grafo, dan valiosa información respecto del grafo o acerca de alguna aplicación que esté siendo modelada con este. Desde sus comienzos, la Teoría Espectral de Grafos ha tenido aplicaciones en Química, Ciencia de la Computación, Optimización Combinatorial y Biología. Se tienen también aplicaciones en Física Teórica y Mecánica Cuántica. Por ejemplo, la energía de un grafo, suma de valores absolutos de los autovalores de la matriz de adyacencia, es intensamente estudiada en Química. Ella puede ser usada para aproximar la π-energía total de una molécula. El presente trabajo de tesis estudia, además, grafos mixtos, los cuales son representados por un diagrama compuesto por vértices y conexiones, donde estas ´ultimas pueden ser “orientadas o no orientadas ”. El Capítulo 1, entrega los conceptos básicos, formalizados matemáticamente, referentes a grafos y a matrices asociadas a estos, presentes en todo el desarrollo de la tesis. En el Capítulo 2 se desarrolla el primer resultado del presente trabajo de tesis. Consiste en la definición de nuevas matrices asociadas a grafos las cuales son una versión unificada de las matrices previamente presentadas para grafos y la determinación de espectros de esas nuevas matrices, junto con el estudio de invariantes espectrales para ciertos grafos. En el Capítulo 3, se introduce la noción de grafo mixto y sobre estos, se desarrollan algunos resultados de la literatura, los cuales, por supuesto, aparecen citados. En el Capítulo 4, se exponen algunos resultados conocidos para el ´índice de Estrada de un grafo no dirigido y el ´índice de Estrada Hermitiano de un grafo mixto. A partir de esto, se define el ´índice Laplaciano mixto y se determinan cotas superiores e inferiores de este invariante espectral, utilizando algunas de las técnicas que se usan para obtener cotas del índice de Estrada de un grafo no dirigido y el índice de Estrada Hermitiano de un grafo mixto. El Capítulo 5, consiste en la definición y determinación de espectros de nuevas matrices asociadas a grafos mixtos, las cuales son una versión unificada de las matrices presentadas previamente para este tipo de grafos. Unido a lo anterior, se estudian invariantes espectrales de ciertos tipos de grafos mixtos.