Restricted connectivity in families of graphs
- Autores: Luis Pedro Montejano Cantoral
- Directores de la Tesis: María Camino Teófila Balbuena Martínez (dir. tes.)
, Pedro García Vázquez (dir. tes.) - Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2011
- Idioma: inglés
- Tribunal Calificador de la Tesis: Josep Fàbrega Canudas (presid.) , Francisco Javier Marcote Ordax (secret.) , Juan Carlos Valenzuela Tripodoro (voc.) , Dirk Meierling (voc.) , Mika Olsen (voc.)
- Texto completo no disponible (Saber más ...)
- Resumen
El objetivo principal de esta tesis ha sido estudiar la conectividad restringida en algunas familias de grafos y digrafos. Se dice que un grafo esta conectado si para cualesquiera dos vértices del grafo existe un camino que los une. Sin duda, es deseable que un grafo permanezca conectado en caso de que se supriman vértices o aristas. Por lo tanto, un problema de gran interés en teoría de grafos consiste en determinar que tan conectado esta un grafo.
La conectividad es una de las nociones básicas en teoría de grafos y existen varias medidas de vulnerabilidad en un grafo G, pero las más representativas son la conectividad por vértices $\kappa(G)$ y la conectividad por aristas $\lambda(G)$. Es conocida la relación entre estos parámetros $\kappa(G)\le\lambda(G)\le\delta(G)$ donde $\delta(G)$ denota el grado mínimo de un vértice. Por lo tanto, es interesante estudiar cuándo un grafo es máximamente conexo ($\kappa(G)=\delta(G)$ o $\lambda(G)=\delta(G)$). Los grafos maximalmente conexos pueden clasificarse de acuerdo a la estructura de sus desconectadores mínimos. De aquí surge la noción de superconectividad, la cuál es uno de los temas más importantes en esta tesis. Se dice que un grafo es superconexo, o superconexo por aristas, si cada desconectador mínimo de vértices o de aristas aísla a un vértice.
Como la conectividad clásica no mide con suficiente precisión que tan conectado está un grafo después de suprimir algunos vértices o aristas, existe interés en estudiar parámetros más refinados que sean más fiables. Incluso dos grafos con la misma conectividad $\kappa$ o $\lambda$ pueden ser considerados con diferentes fiabilidades. La conectividad restringida en un grafo G es definida como la mínima cardinalidad sobre todos los desconectadores restringidos (ya sean de vértices o de aristas) en G, donde un desconectador S es un desconectador restringido si cada componente de G-S tiene al menos 2 vértices.
Hemos estudiado también la k-conectividad restringida por aristas, la cuál es una generalización de la conectividad restringida por aristas y la conectividad restringida por arcos la cuál ha sido definida recientemente para digrafos. Esta nueva noción extiende a digrafos el concepto de la conectividad restringida por aristas en grafos.
Resumiendo, dado un grafo G, hemos estudiado los parámetros $\lambda(G)$, $\kappa(G)$, $\lambda'(G)$, $\lambda_k(G)$, $\kappa_1(G)$ y las nociones de super-$\lambda$, super-$\lambda'$, super-$\lambda_k$ and super-$\kappa$. Más aún, para un digrafo D, se estudió la conectividad restringida por arcos $\lambda'(D)$ y las nociones de superconectividad por arcos (super-$\lambda$) y superconectividad restringida por arcos (super-$\lambda'$).
Las familias de grafos y digrafos consideradas en esta tesis han sido los grafos con diámetro pequeño, grafos con pares de cintura, grafos de polaridad, 3arco-grafos, t-árboles, grafos libres de triángulos, digrafos fuertemente conexos, digrafos s-geodésicos y p-ciclos generalizados El principal objetivo de esta tesis ha sido dar condiciones suficientes para garantizar cotas inferiores, lo más grande posible, para los parámetros mencionados anteriormente. Algunos de los resultados más importantes en esta tesis son los siguientes:
(i) Si $diam(G)\le g-2$ (donde g es la cintura y es impar) y el máximo grado es a lo más $3\delta(G)/2$, entonces el grafo es superconexo.
(ii) Todo grafo G con g con par de cintura (g,h), g impar y h par con $g+3\le h< \infty$ y grado minimo $\delta\ge 3$ es superconexo si $diam(G)\le h-4$.
(iii) Un grafo libre de triángulos de orden $n\ge2k$ es $\lambda_k$-optimal si el grado mínimo es al menos n/4 +k/2 y super-$\lambda_k$ si el grado mínimo es al menos n/4 + (k+1)/2.
(iv) Todo digrafo fuertemente conexo con grado mínimo $\delta\ge2$ es $\lambda'$-conexo y satisface $\lambda'\le\xi'$, donde $\xi'$ grado mínimo de arco.
