Conectando de muchas formas (generalizaciones del concepto de conexidad)

Ponente(s): Diego Antonio Gonzalez Moreno
El concepto de conexidad es uno de los m\'as estudiados dentro de la Teor\'ia de las Gr\'aficas, tanto desde el punto de vista te\'orico como pr\'actico. En el \'ambito de las aplicaciones, se utiliza la conexidad para contruir redes confiables con una alta tolerancia a fallos. Desde el punto de vista te\'orico, se han encontrado una estrecha relaci\'on entre resultados en conexidad y teoremas en otras areas de la Teor\'ia de las Gr'aficas, por ejemplo, el teorema de Hall, sobre emparejamientos en gr\'aficas, o el teorema de Ford-Fulkerson, sobre flujos en redes. Tambi\'en se han encontrado relaciones entre la conexidad, la hamilitonicidad, el di\'ametro, el n\'umero de arboles generadores disjuntos por aristas, etc. La \emph{conexidad por aristas $\lambda (G)$} de una gráfica $G$ se define como la m\'inima cardinalidad de un conjunto de arista que hay que eliminar de la gr\'afica para que esta deje de ser conexa. Obs\'ervese que en \'esta definici\'on no se piden condiciones sobre las componentes conexas o el conjunto de aristas, entonces este concepto se puede extender al imponer condiciones sobre estos conjuntos. Estas "nuevas" definiciones pueden ser de ayuda para obtener par\'ametros m\'as refinados sobre la conexidad de una gr\'afica. La primera generalizaci\'on de este tipo que aparece en la literatura se debe a Harary \cite{2}, quien defini\'o la \emph{$P$-arista-conexidad condicional $\lambda(G, P)$} de una gr\'afica conexa $G$ como la m\'inima cardinalidad de un conjunto de aristas $W$ tal que $G-W$ no es conexa y toda componente de $G-W$ satisface la propiedad $P$. En 1988, Esfahanian y Hakimi \cite{1} introdujeron el concepto de \emph{conexidad restringida de una gr\'afica}, el cual tambi\'en ha sido estudiado bajo el nombre de \emph{superconexidad}. F\`abrega y Fiol \cite{5} definen un tipo de conexidad condicional, la \emph{$k$-conexidad restringida}, la cual consiste en buscar conjuntos de corte no triviales. En lo que respecta a dig\'aficas, Volkmann \cite{6} en el 2007, propone dos tipos de conexidad restringida para digr\'aficas. Tambi\'en existen generalizaciones coloridas, una forma interesante de juntar la conexidad y las coloraciones se debe a Chartrand, Johns, McKeon y Zhang \cite{3}, quienes definieron la conexidad por trayectorias arco\'iris. Una gr\'afica es \emph{conexa por trayectorias arco\'iris} si entre todo par de v\'ertices hay una trayectoria que no utiliza dos aristas del mismo color. Claramente toda gr\'afica conexa tiene una coloraci\'on de sus aristas que la hace conexa por trayectorias arco\'iris (cada arista recibe un color distinto). Entonces, una pregunta interesante es averiguar cu\'al es el m\'inimo n\'umero de colores que puede tener una de \'estas coloraciones. Caro y Yuster \cite{4}, como una pregunta natural y opuesta al problema propuesto por Chartrand et al, estudian el caso monocrom\'atico, es decir, cu\'al es el m\'aximo n\'umero de colores que puede tener una coloraci\'on de forma que entre todo par de v\'ertices exista una trayectoria monocrom\'atica. En esta pl\'atica hablaremos de algunas de estas generalizaciones y platicaremos sobre algunos resultados que hemos obtenido sobre este tipo de conexidades. \vspace*{.1cm} \begin{thebibliography}{11} \bibitem{3} G. Chartrand, G. L. Johns, K. A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem. 133(2008) 85?98. \bibitem{4} Y. Caro, R. Yuster, Colorful monochromatic connectivity, Discrete Math.311 (2011) 1786?1792. \bibitem{1} A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195-199. \bibitem{5} J. F\`abrega and M.A. Fiol. Extraconnectivity of graphs with large girth. Discrete Mathematics, 127 (1994) 163?170. \bibitem{2} F. Harary. Conditional connectivity. Networks, 13 (1983) 347?357. \bibitem{6} L. Volkmann, Restricted arc-connectivity of digraphs, Inform. Process. Lett. 103 (2007) 234-239. \end{thebibliography}