Which Sequences of Iterated Jump Graphs are Planar?
For a graph $G$ of size $m \geq 1$ and
edge-induced subgraphs $F$ and $H$ of size $r$ ($1 \leq r \leq m$),
the subgraph $H$ is said to be obtained from $F$ by an edge jump
if there exist four distinct vertices $u, v, w,$ and $x$ in $G$ such that
$uv \in E(F)$, $wx \in E(G) - E(F)$,
and $H = F - uv + wx$. The minimum number of edge jumps required to
transform $F$ into
$H$ is the jump distance from $F$ to $H$.
For a graph $G$ of size $m \geq 1$ and an integer $r$ with
$1 \leq r \leq m$, the
$r$-jump graph $J_r(G)$ is that graph whose vertices are the
edge-induced subgraphs of size $r$ of $G$ and where two vertices of
$J_r(G)$ are
adjacent if and only if the jump distance
between these subgraphs is 1.
For $k \geq 2$ and $r \geq 1$, the $k$th iterated $r$-jump graph
$J^k_r(G)$ is defined as $J(J^{k-1}_r(G))$, where $J^1_r(G) = J_r(G)$.
An infinite sequence $\{G_k\}$ of graphs
is planar if every graph $G_k$ is planar.
For positive integers $r$ and $k$
and a connected graph $G$ such that
$J_r^k(G)$ is defined for all $k$,
it is shown that $\{J_r^k(G)\}$ is planar
if and only if $(1)$ $r = 1$ and $G = C_5$ or $G$ is the corona of
$K_3$,
$(2)$ $r = 2$ and $G = C_4$, $(3)$ $r = 4$ and $G = C_5$, or $(4)$
$r=5$ and $G$ is the corona of
$K_3$.