El problema de reconstrucción de las gráficas de fichas

Ponente(s): Ana Laura Trujillo Negrete, Ruy Fabila Monroy
Sea $G$ una gráfica de orden $n\ge 2$ y $k\in \{1,2,\dots,n-1\}$. La gráfica de $k$-fichas $F_k(G)$ de $G$ es la gráfica cuyos vértices son los $k$-conjuntos de $V(G)$ y en donde dos $k$-conjuntos son adyacentes si su diferencia simétrica es un par de vértices adyacentes en $G$. En 2012 Ruy Fabila-Monroy et al. conjeturaron lo siguiente: Si $G$ y $H$ son dos gráficas tales que $F_k(G)$ y $F_k(H)$ son isomorfas para algún $k$, entonces $G$ y $H$ son isomorfas. En esta plática mostraremos que esta conjetura es cierta para la familia de gráficas libres de $4$-ciclos y diamantes (un $4$-ciclo con una cuerda) y cualquier $k$ admisible. Más aún, mostraremos que para cualquier $G$ en esta familia es posible reconstruir a $G$ a partir de su gráfica de $k$-fichas, y si además $G$ es conexa, dicha reconstrucción puede hacerse en tiempo polinomial.