Resumen de Fault tolerance results for some families of graphs

Diego Antonio Gonzalez Moreno

• The main objective of this thesis is to study some fault-tolerance results in some families of graphs, The fault-tolerance of a network is the property that enables it to continue working when some of its components fails. Usually, networks and thus their representing graphs are connected; that is, there exists a path between every two vertices in the graph. Clearly, it is desirable that a network stays connected in case faults should arise. In this thesis we mainly study a fault-tolerance measure in graphs (corresponding to the removal of vertices or edges): the (vertex or edge) k-restricted connectivity, dened as the minimum number of vertices or edges which must be removed such that the resulting graph is disconnected and the survival components contain at least k vertices. As particular cases 1-restricted (vertex or edge) connectivities are just the standard connectivities ¿ and ¿. The families of graphs that we mainly study are Permutation Graphs, Cages and (D;g)-cages.

  For Permutation Graphs we establish upper and lower bounds for the k-restricted edge connectivity when k=2,3, and we look for some conditions for guaranteeing optimal values. Some other results on the k-restricted edge connectivity of K4 -free graphs and t-trees are also given.

  An (r;g)-cage (for short, a cage) is an r-regular graph with girth g and the least possible number of vertices. In this thesis an upper bound for the order of some (r;g)-cages is given first. Furthermore, some new results on the connectivity for some families of cages are presented.

  A (D;g)-cage is a graph with degree set D, girth g and with the least possible number of vertices. When D={r}, (D;g)-cages coincide with (r;g)-cages. The goal of this part of the thesis is to approach some structural properties of (D;g)-cages, as a natural extension of the known properties of (r;g)-cages.

  Semiregular cages (D={r,r+1}) are mainly studied in this thesis, obtaining results for their order, diameter, and vertex and edge connectivity.

  El principal objetivo de esta tesis es el estudio de la tolerancia a fallos en algunas familias de grafos. La tolerancia a fallos de una red es la propiedad que permite que ésta siga funcionando cuando algunas de sus componentes fallan.

  Usualmente las redes y por tanto los grafos que las modelan son conexos; es decir, para todo par de vértices del grafo hay un camino entre ellos. Es deseable que una red se mantenga conexa si algún fallo se produce. En esta tesis, estudiamos principalmente una medida de tolerancia a fallos en grafos (correspondiente a la eliminación de vértices o aristas): la k-conexidad restringida por vértices o aristas, definida como el mínimo número de vértices o aristas que deben eliminarse para que el grafo resultante no sea conexo y las componentes restantes contengan al menos k vértices. Como casos particulares la 1-conexidad restringida (por vértices o aristas) corresponde a las conexidades estándar ¿ y ¿. La familias de grafos que estudiamos principalmente son los Grafos Permutación, las Jaulas y las (D;g)-jaulas.

  Para los Grafos Permutación establecemos cotas superiores e inferiores para la k-conexidad restringida por aristas cuando k=2,3, y buscamos algunas condiciones para garantizar valores óptimos. También se presentan otros resultados sobre la k-conexidad por aristas de los grafos libres de K4 y de los t-árboles.

  Una (r;g)-jaula (de forma abreviada, una jaula) es un grafo r-regular con cintura g y el menor número posible de vértices. En esta tesis damos en primer lugar un nueva cota superior para el orden de algunas (r; g)-jaulas. Además, se dan algunos nuevos resultados sobre la conexidad de ciertas familias de jaulas.

  Una (D;g)-jaula es un grafo con conjunto de grados D, cintura g y el menor número posible de vértices. Cuando D={r}, las (D;g)-jaulas coinciden con las (r; g)-jaulas. El objetivo de esta parte de la tesis es abordar el estudio de algunas propiedades estructurales de las (D;g)-jaulas, como una extensión natural de las propiedades conocidas de las jaulas. En esta tesis se estudian básicamente las jaulas semirregulares (D={r,r+1}), obteniendo resultados para el orden, el diámetro, y la conexidad por vértices o aristas.