Rotation and jump distances between graphs

• Autorzy: Gary Chartrand , Heather Gavlas , Héctor Hevia , Mark A. Johnson
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

edge rotation; rotation distance; edge jump; jump distance; jump distance graph

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1997
• Tom: 17
• Numer: 2
• Strony: 285-300

Daty

wydano

1997

otrzymano

1996-08-16

poprawiono

1997-07-02

Twórcy

autor

Gary Chartrand

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

autor

Heather Gavlas

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

autor

Héctor Hevia

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

autor

Mark A. Johnson

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1056