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.

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