Tesis Doctorado
Espectros de grafos compuestos y aplicaciónes
Autor
Rojo-Jeraldo, Oscar
Universidad Católica del Norte
Institución
Resumen
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.