Planarity of 3,4-jump Graphs

【摘要】 <正>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更多还原

【Abstract】 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 graph of a graph G, {J4k(G)} is planar if and only if G = C5. For r ≥ 5, whether the fix graph of the sequence {Jrk(G)} exists is determined.更多还原