3,4跳图的平面性

For a graph G of size ε≥1 and its edge-induced subgraphs H1 and H2 of size r(1≤r≤ε), H1 is said to be obtained from H2 by an edge jump if there exist four distinct vertices u,v,w and x in G such that (u,v)∈E(H2), (w,x)∈ E(G)-E(H2) and H1=H2-(u,v)+(w,x). In this article, the r-jump graphs (r≥3) are discussed. A graph H is said to be an r-jump graph of G if its vertices correspond to the edge induced graph of size r in G and two vertices are adjacent if and only if one of the two corresponding subgraphs can be obtained from the other by an edge jump. For k≥2, the k-th iterated r-jump graph Jrk(G) is defined as Jr(Jrk-1(G)), where Jr1(G)=Jr(G).An infinite sequence{Gi} of graphs is planar if every graph Gi is planar. It is shown that there does not exist a graph G for which the sequence {J3k(G)} is planar, where k is any positive integer. Meanwhile,lim gen(J3k(G))=∞,where gen(G) denotes the genus of a graph G, if the sequencek→∞J3k(G) is defined for every positive integer k. As for the 4-jump gra

Planarity of 3,4-jump Graphs