Rotation and jump distances between graphs

Chartrand, Gary ; Gavlas, Heather ; Hevia, Héctor ; Johnson, Mark

Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 2, pp. 285-300

Résumé

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 ∉ 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∉ 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 d_j(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 d_r(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 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 D_j(S) of S has S as its vertex set and where G₁ and G₂ in S are adjacent if and only if d_j(G₁,G₂) = 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 D_j(S) = G. Several graphs are shown to be jump distance graphs, including all complete graphs, trees, cycles, and cartesian products of jump distance graphs.

Détail

Keywords: edge rotation, rotation distance, edge jump, jump distance, jump distance graph