Reconstruction of token graphs.

Abstract: Let $G$ be a graph of order $n\ge 2$, and let $k$ be an integer with $k\in \{1,2,\dots,n-1\}$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are all the $k$-subsets of vertices of $G$, and two of such $k$-subsets are adjacent whenever their symmetric difference is an edge of $G$. We denote by $C_4$ the $4$-cycle and by $D_4$ the diamond graph (a $4$-cycle with a chord). We say that $G$ is a $(C_4,D_4)$-free graph if $G$ does not contain $C_4$ nor $D_4$ as a subgraph.

In 2012 Fabila-Monroy et al. conjectured the following: If $G$ and $H$ are two graphs such that $F_k(G)$ and $F_k(H)$ are isomorphic for some $k$, then $G$ and $H$ are isomorphic. In this talk we will show this conjecture for the family of $(C_4,D_4)$-free graphs. Moreover, we will see how this reconstruction problem is related to the automorphism group of token graphs. This is a joint work with Ruy Fabila Monroy.

Posted on Oct 24, 2022 in ACGO, Seminars