Tesis doctoral de Julián Salas Piñón
El objeto de estudio de esta tesis son las jaulas, algunas de sus propiedades, y construcciones de familias de dichos grafos. El estudio de grafos sin ciclos cortos juega un papel fundamental para adquirir conocimiento de su estructura con el fin de, posteriormente, ser capaces de abordar los problemas en jaulas. Las jaulas fueron introducidas por tutte en 1947. En 1963, erdí¶s y sachs probaron que las (k; g) -jaulas existen para cualesquiera valores de grado k y cintura g. Desde entonces, gran cantidad de la investigación en jaulas se ha enfocado a construirlas. En este trabajo estudiamos propiedades estructurales tales como la conectividad, diámetro, y la regularidad de grafos sin ciclos cortos. En cierto sentido la conectividad es una medida de la fiabilidad de una red. Dos grafos con la misma conectividad por aristas, pueden tener diferentes fiabilidades, la superconectividad por aristas y las conectividades restringidas han sido propuestos como un índice más refinado de fiabilidad que la conectividad por aristas. Relajando las condiciones que se requieren para que un grafo sea jaula, se obtienen propiedades de conectividad más refinadas en esas familias y a su vez, se tiene una aproximación a las propiedades estructurales de las familias con más restricciones (i.E., Las jaulas). Nuestro objetivo al estudiar propiedades estructurales tales como la conectividad en jaulas es obtener una visión más profunda en cuanto a su estructura, para posteriormente ser capaces de atacar el problema de su construcción. A modo de ejemplo, estudiamos una condición en el diámetro con relación al par de cinturas de un grafo, y como corolario, obtuvimos un resultado que garantiza la conectividad restringida de una familia espacial de grafos que vienen de la geometría, como son los grafos de polaridad. Asimismo, obtuvimos un resultado probando la super-conectividad por aristas de jaulas semiregulares. Con base en estos trabajos nos fue posible desarrollar el estudio de las jaulas. De manera que obtuvimos un resultado relevante con respecto a su conectividad, esto es, que las (k; g)-jaulas son k/2-conexas. También, a raíz del trabajo previo en pares de cinturas, obtuvimos construcciones de grafos regulares pequeños con un par de cinturas dado, respondiendo la pregunta de harary y kovács que relaciona el orden de las (k; g, h)-jaulas con el de las jaulas, para casi todos los casos. El concepto de grafo de moore, con relación al grado y al diámetro, fue introducido por hoffman and singleton, posteriormente a edward f. Moore, que fue quien propuso la pregunta de describir y clasificar dichos grafos. Además de tener el máximo número posible de vértices para una combinación de grado y diámetro dada, los grafos de moore tienen el mínimo número posible de vértices para un grafo con cintura y grado dados. Esto es, los grafos de moore son jaulas. La formula para el número de vértices de un grafo de moore se puede generalizar para incluir grafos con cintura par (grafos de moore bipartitos) además de los grafos de cintura impar, y nuevamente dichos grafos son jaulas. De este modo, los grafos de moore nos dan una cota inferior para el orden de las jaulas, pero solo existen para valores específicos de k, por lo tanto es interesante estudiar que tan lejos está una jaula de dicha cota, este parámetro es llamado el exceso de una jaula. En este trabajo presentamos algunas relaciones y resultados con respecto al exceso de una jaula y dimos una contribución, en el sentido de biggs e ito, relacionando la bipartición de las jaulas de cintura 6 con sus órdenes. Los grafos que cumplen la cota de moore para cinturas g=6, 8, 12, se obtienen de los grafos de incidencia de geometrías finitas, por ejemplo, los grafos de incidencia de planos proyectivos de orden q potencia de primo son las (q+1, 6)-jaulas. Usando otras estructuras de incidencia tales como los cuadrángulos generalizados o los hexágonos generalizados se obtienen familias de jaulas de cinturas 8
Datos académicos de la tesis doctoral «On the structure of graphs without short cycles«
- Título de la tesis: On the structure of graphs without short cycles
- Autor: Julián Salas Piñón
- Universidad: Politécnica de catalunya
- Fecha de lectura de la tesis: 20/12/2012
Dirección y tribunal
- Director de la tesis
- M. Camino Teófila Balbuena Martínez
- Tribunal
- Presidente del tribunal: josep Fí brega canudas
- domenico Labbate (vocal)
- pedro García vázquez (vocal)
- María Bras amorós (vocal)