Discussiones Mathematicae Graph Theory  17(2) (1997)  285-300
doi: 10.7151/dmgt.1056

[BIBTex] [PDF]

ROTATION AND JUMP DISTANCES BETWEEN GRAPHS

Gary Chartrand

Department of Mathematics and Statistics
Western Michigan University, Kalamazoo, MI 49008, USA

Heather Gavlas

Smiths Industries, Defense Systems North America
Grand Rapids, MI 49518-3469, USA


Héctor Hevia

Escuela de Ingenieria Comercial, Universidad Adolfo Ibanez
Balmaceda 1625, Vina del Mar, CHILE


Mark A. Johnson

Pharmacia & Upjohn, 7247-267-133
301 Henrietta Street, Kalamazoo, MI 49007, USA

Abstract

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

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

1991 Mathematics Subject Classification: Primary: 05C12, Secondary: 05C75.

References

[1] V. Balá, J. Koa, V. Kvasnika and M. Sekanina, A metric for graphs, asopis Pst. Mat. 111 (1986) 431-433.
[2] G. Benadé, W. Goddard, T.A. McKee and P.A. Winter, On distances between isomorphism classes of graphs, Math. Bohemica 116 (1991) 160-169.
[3] G. Chartrand, W. Goddard, M.A. Henning, L. Lesniak, H.C. Swart and C.E. Wall, Which graphs are distance graphs? Ars Combin. 29A (1990) 225-232.
[4] G. Chartrand, F. Saba and H-B Zou, Edge rotations and distance between graphs, asopis Pst. Mat. 110 (1985) 87-91.
[5] R.J. Faudree, R.H. Schelp, L. Lesniak, A. Gyárfás and J. Lehel, On the rotation distance of graphs, Discrete Math. 126 (1994) 121-135, doi: 10.1016/0012-365X(94)90258-5.
[6] E.B. Jarrett, Edge rotation and edge slide distance graphs, Computers and Mathematics with Applications, (to appear).
[7] C. Jochum, J. Gasteiger and I. Ugi, The principle of minimum chemical distance, Angewandte Chemie International 19 (1980) 495-505, doi: 10.1002/anie.198004953.
[8] M. Johnson, Relating metrics, lines and variables defined on graphs to problems in medicinal chemistry, in: Graph Theory With Applications to Algorithms and Computer Science, Y. Alavi, G. Chartrand, L. Lesniak, D.R. Lick, and C.E. Wall, eds., (Wiley, New York, 1985) 457-470.
[9] V. Kvasnika and J. Pospichal, Two metrics for a graph-theoretic model of organic chemistry, J. Math. Chem. 3 (1989) 161-191, doi: 10.1007/BF01166047.