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$.