Hamiltonicidad en Algunas Gráficas de Fichas

Ponente(s): Luis Enrique Adame Martínez, Dr. Luis Manuel Rivera Martínez, Dr. José Manuel Gómez Soto

Dada una gr\'afica $G$ y un entero $k \in \{ 1,2, \ldots , n-1\}$, se define {\bf la gr\'afica de $k$-fichas de G}, denotada por $G^{(k)}$, como la gr\'afica donde sus v\'ertices son todos los k-conjuntos de $V(G)$, y dos v\'ertices $A$ y $B$ de $G^{(k)}$ son adyacentes si $A\Delta B=\{a,b\} \in E(G)$.\\ Esta clase de gr\'aficas se han estudiado al menos desde los 80's por diversos autores. El inter\'es por las propiedades de estas gr\'aficas ha aumentado recientemente por sus posibles aplicaciones en \'areas tales como teor\'ia de c\'odigos y f\'isica cu\'antica.\\ En esta pl\'atica se presentar\'an algunos resultados, sobre la hamiltonicidad en gr\'aficas de $k$-fichas. En particular sobre un resultado original, que caracteriza la hamiltonicidad de las gr\'aficas de dos fichas de la gr\'afica abanico $F_{m,n}$,que se define como la suma (join graph) de $\overline{K_m}$ y $P_n$. En parte de la demostraci\'on de dicho resultado se propone un algoritmo.