Subgraph distances in graphs defined by edge transfers (Q1363654)

A graph \(G\) and its edge-induced subgraphs having the same number \(k\) of vertices are considered. If \(F\) and \(H\) are such subgraphs, \(H\) is said to be obtained from \(F\) by an edge jump, if there exist four pairwise distinct vertices \(u\), \(v\), \(w\), \(x\) such that \(uv\in E(F)\), \(wx\in E(G)- E(F)\) and \(H= F-uv+wx\). One says that \(F\) can be \(j\)-transformed into \(H\), if \(H\) can be obtained from \(F\) by a finite number of edge jumps. A necessary and sufficient condition for a graph to have the property that any edge-induced subgraph with \(k\) vertices of \(G\) can be \(j\)-transformed into any other one is stated. The \(k\)-jump graph \(J_k(G)\) is defined so that its vertex set is the set of all edge-induced subgraphs of \(G\) with \(k\) vertices and two vertices are adjacent in it if and only if one of them is transformed into the other by one jump. Iterations of the jump graph are studied, it is described when the sequence of such iterations converges, when it diverges and when it terminates. At the end, the hamiltonicity of jump graphs is investigated.