Publication: Estudio de la constante de hiperbolicidad en grafos
Loading...
Identifiers
Publication date
2011
Defense date
2011-05-23
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
Esta tesis se dedica al estudio de los grafos hiperbólicos y está dividida en cuatro capítulos.
El primer capítulo es una intoducción a la teoría de grafos y a los espacios hiperbólicos en sentido de Gromov. En los demás capítulos se incluyen los resultados de investigación que hemos conseguido.
Aunque se dispone de ejemplos interesantes de espacios hiperbólicos, no existen criterios generales que permitan determinar la hiperbolicidad de un espacio. Por tanto, uno de los problemas más importantes en el estudio de los grafos hiperbólicos es obtener criterios que garanticen si un determinado grafo es hiperbólico o no.
Por otra parte, existen numerosos parámetros en teoría de grafos que tienen gran importancia, tales como: el número de vértices, el núumero de aristas, el grado máximo, el grado mínimo, el diámetro, el cuello,... Por tanto, otro problema tan natural como importante es encontrar desigualdades que relacionen alguno de estos parámetros (o varios de ellos simultáneamente) con la constante de hiperbolicidad del grafo, encontrando y clasificando (como es importante en teoría de grafos) aquellos grafos para los que se tenga la igualdad.
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ñadiendo 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.
Description
Keywords
Grafos hiperbólicos