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


Subgraph distances in graphs defined by edge transfers
Authors:Gary Chartrand  H  ctor Hevia  Elzbieta B Jarrett and Michelle Schultz
Institution:

a Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA

b Universidad Católica de Valparaiso, Chile

c Modesto Junior College, USA

d University of Nevada Las Vegas, Las Vegas, NV 89121, USA

Abstract:For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E(F), wx ε E(G) - E(F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J(G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{Jk(G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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