On Realizing Reconfiguration Graphs of Cliques
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916071653507072 |
|---|---|
| author | Hoang, Duc A. |
| author_facet | Hoang, Duc A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03567 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Realizing Reconfiguration Graphs of Cliques Hoang, Duc A. Combinatorics Discrete Mathematics 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. |
| title | On Realizing Reconfiguration Graphs of Cliques |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2604.03567 |