首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On the planarity of jump graphs
Authors:Hctor Hevia  Donald W VanderJagt  Ping Zhang
Institution:

a Escuela de Ingenieria Comercial, Universidad Adolfo Ibanez, Balmaceda 1625, Vina del Mar, Chile

b Department of Mathematics and Statistics, Grand Valley State University, Allendale, MI 49401, USA

c Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA

Abstract:For a graph G of size mgreater-or-equal, slanted1 and edge-induced subgraphs F and H of size k (1less-than-or-equals, slantkless-than-or-equals, slantm), 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 uvset membership, variantE(F), wxset membership, variantE(G)−E(F), and H=Fuv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size mgreater-or-equal, slanted1 and an integer k with 1less-than-or-equals, slantkless-than-or-equals, slantm, the k-jump graph Jk(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of Jk(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J2(G) is planar are determined.
Keywords:k-jump distance  k-jump graph  Planar graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号