DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

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.