Grafos con tamaño máximo y cintura inferiormente acotada

Abstract

Uno de los estudios más representativos dentro de la Teoría Extremal de Grafos es la determinación, en función del orden, del tamaño máximo de un grafo que no contiene como subgrafo a un grafo o a una familia de grafos dada. En 1941 Turán, uno de los promotores del posterior desarrollo de la Teoría Extremal de Grafos, determina el tamaño máximo de un grafo que no contiene a un subgrafo completo. Asimismo caracteriza los grafos extremales asociados a dicho problema, dando lugar a los que se conocen como grafos de Turán. En este contexto se encuadra esta tesis. En concreto, estudiamos el tamaño máximo que puede alcanzar un grafo de orden dado sin que se formen ciclos de longitud menor o igual que un entero preestablecido. Pocos son los resultados conocidos hasta este momento de esta función. En los años 1978 y 1982, B. Bollobás, P. Erdös y M. Simonovits obtienen cotas superiores de ella. En 1983 P.Erdös proporciona cotas inferiores que son mejoradas en 1995 por F. Lazebnik, V.A. Ustimenko y A.J. Woldar. La búsqueda de soluciones exactas ha sido escasamente abordada y casi se reduce al caso de grafos que no contienen ni triángulos ni cuadrados. En este sentido, D.K. Garnick, Y.H.Kwong, F. Lazebnik y N.A.~Nieuwejaar obtienen en los años 1992 y 1993 los valores exactos cuando los grafos tienen a lo sumo 30 vértices o exactamente 50 vértices. Debido a la dificultad que conlleva la resolución del problema planteado, diversos autores han estudiado propiedades comunes a los grafos extremales, en especial las relativas a conectividad, diámetro, cintura... En particular, en 1997 F. Lazebnik y P. Wang cuestionan la existencia de ciclos de longitud n+1 en todo grafo extremal sin ciclos de longitud menor o igual que n. Desde entonces, varios son los artículos que han tratado esta cuestión. Siguiendo con estas líneas de trabajo, esta tesis se ha centrado en: i) la obtención de valores exactos de la función extremal ii) la caracterización de las familias de grafos extremales, iii) el estudio de propiedades de los grafos extremales.