Estudio de la constante de hiperbolicidad en grafos

Resumen

En esta tesis se demuestra que el estudio de la hiperbolicidad de los grafos se puede reducir al estudio de la hiperbolicidad de grafos más sencillos. En particular, hemos demostrado que el estudio de la hiperbolicidad de un grafo G con lazos y aristas múltiples se puede reducir al estudio de la hiperbolicidad del grafo obtenido al eliminar de G sus lazos y aristas múltiples; también se demuestra que el estudio de la hiperbolicidad de un grafo arbitrario es equivalente al estudio de la hiperbolicidad de un grafo 3-regular obtenido añdiendo algunas aristas y vértices. En resumen, probamos que el estudio de la hiperbolicidad para grafos generales (posiblemente con lazos y aristas múltiples) se reduce al estudio de la hiperbolicidad de grafos cúbicos sin lazos ni aristas múltiples. Adicionalmente, se estudia cómo la constante de hiperbolicidad de un grafo puede cambiar añadiendo o eliminando una cantidad finita o infinita de aristas. Por otra parte, se obtienen buenas cotas de la constante de hiperbolicidad de un grafo y los valores exactos de esta constante para algunas familias importantes de grafos. En particular, se investiga la relación entre la constante de hiperbolicidad de un grafo G y su número de aristas, su diámetro y sus ciclos. Finalmente, encontramos condiciones para que un grafo que sea el 1-esqueleto de una teselación de una superficie riemaniana sea hiperbólico. Se demuestra que los isomorfismos entre grafos no siempre preservan la hiperbolicidad y, de hecho, encontramos condiciones suficientes para que dos grafos isomorfos sean equivalentes en términos de la hiperbolicidad. Por último, demostramos que un grafo es hiperbólico si y sólo si su grafo dual es hiperbólico.