On Realizing Reconfiguration Graphs of Cliques

Abstract

For a graph $H$ and an integer $k\ge 1$, the \emph{Token Sliding reconfiguration graph} ${\mathsf{TS}}_k(H)$ and the \emph{Token Jumping reconfiguration graph} ${\mathsf{TJ}}_k(H)$ have as vertices the $k$-cliques of $H$, with two vertices adjacent when one clique is obtained from the other by replacing one vertex with an adjacent non-member, and respectively by an arbitrary non-member. For a target graph $G$, we study the feasibility sets ${\mathcal{K}}^{\mathsf{TS}}(G)$ and ${\mathcal{K}}^{\mathsf{TJ}}(G)$, consisting of all integers $k$ for which $G$ is isomorphic to ${\mathsf{TS}}_k(H)$ and ${\mathsf{TJ}}_k(H)$, respectively, for some graph $H$. We determine the exact feasibility sets for complete graphs, paths, cycles, complete bipartite graphs, book graphs, friendship graphs, and their complements, and give complete classifications for all Johnson graphs.

37 pages, 7 figures, v2: revision of v1, add figures, revise proofs