On the Planarity of Iterated Jump Graphs
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 correspond to 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 the corresponding 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_i\}$ of graphs
is planar if every graph $G_i$ is planar.
All graphs $G$ for which $\{J^k_r(G)\}$
($r = 1, 2$) is planar are determined and it is shown that
if the sequence $\{J^k_r(G)\}$ is nonplanar, then
$\lim_{k \rightarrow \infty} gen(J^k_r(G)) = \infty,$
where $\gen(G)$ denote the genus of a graph $G$.