Planarity Of Jump Graph

Let G be a simple graph, the line graph G, denoted L(G), is the graph whose verticesare the edges of G, with two vertices of L(G) adjacent if and only if the correspondingedges are adjacent in G.Chartrand et al. [2] introduced a type of transformation graph, called k-jump graphJk(G). The vertex set of Jk(G) consists of all subgraphs of size k, and two vertices H andF are adjacent in Jk(G) if and only if there exists four vertices u, v, w, x in G such thatuv∈E(F), wx∈E(G)?E(F) and H = F ?uv +wx. Obviously, if J1(G) = L(G), andJ1(G) is called the jump graph of G. In fact, jump graphs have many nice properties, suchas small diameter, large connectivity. Chartrand et al. [2] proved that the diameter of aconnected jump graph is at most 4. Wu and Meng [12] showed that the connectivity ofa connected jump graph is at least its minimum degree minus one, and give a necessaryand su?cient condition for a jump graph to be hamiltonian. Wu et al. [11] presenta necessary and su?cient condition for a graph G whose jump graph J(G) is Supper-connected and hyper-connected, respectively. H′ector Hevia et al. [5] characterizes allplanar J2(G). Chartrand et al. [3] characterized all graphs G, whose iterated jump areoften planar. Wei and Liu [10] investigated the planarity of Jk(G) when k = 3 or k = 4.In this thesis, we give a necessary and su?cient for J(G) being planar.The paper consists of two chapters. In Chapter I, as an introduction, we introducesome definition, background and our main results. The second chapter is the proof of thetheorem, which is divided into two sections. In the first section, we present some theoremsand corollaries used in the proof of main theorem and in the second section, shall give theproof of main theorem.