Rotation and jump distances between graphs

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u, v, and w such that uv ∈ E(G), uw 6∈ E(G), and H = G − uv + uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u, v, w, and x such that uv ∈ E(G), wx 6∈ E(G), and H = G − uv + wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H . It is shown that for every two graphs G and H of the same order (at least 5) and same size, G can be j-transformed into H . For every two graphs G and H of the same order and same size, the jump distance dj(G, H) between G and H is defined as the minimum number of edge jumps required to j-transform G into H . The rotation distance dr(G, H) between two graphs G and H of the same order and same size is the minimum number of edge rotations needed to transform G into H . The jump 1 Research supported in part by Office of Naval Research Grant N00014-91-J-1060. 2 Research supported in part by FONDECYT under Project 1941219 (94). 286 G. Chartrand, H. Gavlas, H. Hevia and M.A. Johnson and rotation distances of two graphs of the same order and same size are compared. For a set S of graphs of a fixed order at least 5 and fixed size, the jump distance graph Dj(S) of S has S as its vertex set and where G1 and G2 in S are adjacent if and only if dj(G1, G2) = 1. A graph G is a jump distance graph if there exists a set S of graphs of the same order and same size with Dj(S) = G. Several graphs are shown to be jump distance graphs, including all complete graphs, trees, cycles, and cartesian products of jump distance graphs.