Espectros de grafos compuestos y aplicaciónes

Abstract

Esta Tesis tiene como tema general la Teoría Espectral de Grafos, principalmente el estudio del espectro de la matriz Laplaciana y matriz de adyacencia asociadas a ciertos tipos de grafos. Desarrollamos esta Tesis en 6 Capítulos. En el Capítulo 1 entregamos algunos conceptos de la Teoría de Grafos y la Teoría de Matrices, requeridos para el desarrollo de la Tesis. En el Capítulo 2, caracterizamos los autovalores de la matriz Laplaciana y la matriz de adyacencia de un grafo ponderado con raíz obtenido de un árbol ponderado Bethe generalizado de k niveles y diques ponderados por niveles. Estos autovalores son los autovalores de matrices tridiagonales simétricas de orden j xj, 1 s j s k. Además, damos resultados sobre la multiplicidad de los autovalores, radios espectrales y conectividad algebraica. En los Capítulos 3 y 4 caracterizamos los espectros de nuevos grafos. Estos grafos son obtenidos a partir de un conjunto de grafos ponderados Bethe generalizados con diques ponderados por niveles, en primer lugar unidos por su respectivo vértice raíz a los vértices de un grafo ponderado y después identificando sus vértices raíces. Como antes, damos informción respecto de las multiplicidades de sus autovalores e información sobre sus radios espectrales. Nuevamente sus autovalores son los autovalores de matrices simétricas de orden mucho menor que el orden del grafo y casi todas son tridiagonales. En el Capítulo 5 presentamos resultados obtenidos sobre la conectividad algebraica de un tipo especial de árboles llamados caterpillars. Para una cierta clase de caterpillars, caracterizamos sus autovalores Laplacianos y damos una cota superior para la conectividad algebraica. Además, ordenamos por conectividad algebraica algunas subclases y mostramos los caterpillars con la menor y la mayor conectividad algebraica. Finaliza la Tesis, con el Capítulo 6, entregando un aporte en el tema de energía de grafos. Dado un grafo bipartito g con energía E, construimos un nuevo grafo bipartito, mediante r copias de g, con energía yr E. La técnica empleada permite la construcción de pares de grafos bipartitos no isomorfos con la misma energía.