Reconstrucción de algunas gráficas a partir de su gráfica de 2-fichas

Ponente(s): Ana Laura Trujillo Negrete, Ruy Fabila Monroy, Wolfgang Mulzer, Perouz Taslakian, Stefanie Wuhrer

Sea G una gráfica de orden n y sea k un entero entre 1 y n-1. La gráfica de k-fichas de G es la gráfica cuyos vértices son todos los k-conjuntos de V(G) y donde dos k-conjuntos de V(G) son adyacentes si su diferencia simétrica es un par de vértices adyacentes en G. En el año 2012 Ruy Fabila et al. conjeturaron que si G y H son dos gráficas tales que sus gráficas de k-fichas son isomorfas para algún k, entonces G y H son isomorfas. El objetivo de esta plática es presentar un bosquejo a la demostración de que si G es una gráfica conexa que no tiene como subgráfica inducida a un prisma triangular, entonces G puede reconstruirse a partir de su gráfica de 2-fichas.