Ir al contenido

Documat


Resumen de Some contributions to the study of the connectedness of graphs and digraphs

Francisco Javier Marcote Ordax Árbol académico

  • Esta tesis trata sobre el estudio de la conectividad tanto de digrafos sin autolazos como de los grafos regulares llamados genéricamente cages, presentando nuevas contribuciones en estos campos. Siendo más precisos, el objetivo principal es proporcionar cotas inferiores tan grandes como sea posible para sus parámetros conectividad, arco-(rama-)conectividad, superconectividad y arco-(rama-)superconectividad, parámetros que son apropiados para cuantificar su "grado de conectividad".

    Para digrafos sin autolazos, las cotas inferiores que se presentan para estos parámetros se han obtenido asumiendo que cada digrafo satisface cierta "condición estructural", que se escribe en términos de un parámetro relacionado con el número de caminos cortos y, o bien diámetro, o bien un cierto diámetro condicional. A partir de este estudio, hemos conseguido presentar condiciones para que un digrafo sea maximalmente conectado, maximalmente arco-conectado, superconectado o arco-superconectado, ampliando el rango de digrafos para los que se pueden encontrar resultados similares en trabajos previos.

    La segunda parte de la tesis aborda el estudio de la conectividad de cages, presentando nuevas contribuciones en este entorno. Una cage es un grafo regular tal que su orden es el menor entre todos aquellos grafos regulares que tienen su mismo grado y girth. Aunque es bien sabido que las cages existen para cualquier valor del grado y del girth, su construcción no ha sido posible excepto para un número reducido de casos, desde que fueron definidas en 1947.

    Sin embargo, la conectividad de las cages ha sido estudiada en los últimos años, habiéndose obtenido como principal resultado que son 3-conexas. Nuestras contribuciones siguen básicamente dos direcciones.

    En primer lugar, en relación al parámetro conectividad, demostramos que casi todas las cages son 4-conexas, que toda cage con girth 6 u 8 y que un buen número de cages con girth 5 son máxi


Fundación Dialnet

Mi Documat