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