Subgraph distances in graphs defined by edge transfers

✍ Scribed by Gary Chartrand; Héctor Hevia; Elzbieta B. Jarrett; Michelle Schultz

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 800 KB
• Volume: 170
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00357-3

✦ Synopsis

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 ifH 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.