Hamiltonicidad en gráficas de 2-fichas de la suma de gráficas

Autor: Luis Enrique Adame Martínez
Coautor(es): Luis Manuel Rivera Martínez, Ana Laura Trujillo Negrete
Sea $G$ una gr\'afica de orden $n$. La gráfica de $k$-fichas de $G$, denotada por $F_k(G)$, es la gr\'afica cuyo conjunto de v\'ertices son todos los $k$-conjuntos de $V(G)$ y donde dos v\'ertices $A$ y $B$ en $F_k(G)$ son adyacentes si y solo si $A \triangle B = \{a, b\} \in E(G)$. El estudio de las propiedades combinatorias de las gr\'aficas de fichas data de los 80's (caso $k=2$) pero recientemente han llamado la atenci\'on a varios grupos de investigadores, entre otras cosas por sus posibles aplicaciones. En esta platica se presentan algunos resultados sobre la Hamiltonicidad de la gr\'afica de $2$-fichas de la suma de dos gr\'aficas $G_1$ y $G_2$. En particular se demuestra que si $G_1=\overline{K_m}$ y $G_n$ es cualquier gr\'afica con un camino Hamiltoniano, entonces la gráfica de $2$ fichas de $\overline{K_m}+G_n$ es Hamiltoniana si y solo si $n \geq 2$ y $1\leq m \leq 2n$.