Combinatorics Seminar - Ruy Fabila Monroy

16:15-18:00

Speaker: Ruy Fabila Monroy

Title: Token graph reconstruction in Diamond and C_4 free graphs

Abstract: Let G be a graph on n vertices and 0< k <n be an integer. The k-token graph
F_k(G) is the graph whose vertex set are all the k-subsets of vertices of G, two of which are
adjacent when their symmetric difference is an edge of G. An open problem is whether
the token graph determines G. That is, if F_k(G) is isomorphic to F_k(H), does this imply
that G and H are isomorphic. In this talk we show that this is the case for diamond and C_4 free
connected graphs. We also introduce a notion of when a graph is uniquely reconstructible from its token graph;
and show how this notion is related to the automorphism groups of G and F_k(G).