# Rotation and jump distances between graphs

Gary Chartrand; Heather Gavlas; Héctor Hevia; Mark A. Johnson

Discussiones Mathematicae Graph Theory (1997)

- Volume: 17, Issue: 2, page 285-300
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGary Chartrand, et al. "Rotation and jump distances between graphs." Discussiones Mathematicae Graph Theory 17.2 (1997): 285-300. <http://eudml.org/doc/270366>.

@article{GaryChartrand1997,

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 $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.},

author = {Gary Chartrand, Heather Gavlas, Héctor Hevia, Mark A. Johnson},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge rotation; rotation distance; edge jump; jump distance; jump distance graph},

language = {eng},

number = {2},

pages = {285-300},

title = {Rotation and jump distances between graphs},

url = {http://eudml.org/doc/270366},

volume = {17},

year = {1997},

}

TY - JOUR

AU - Gary Chartrand

AU - Heather Gavlas

AU - Héctor Hevia

AU - Mark A. Johnson

TI - Rotation and jump distances between graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1997

VL - 17

IS - 2

SP - 285

EP - 300

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

LA - eng

KW - edge rotation; rotation distance; edge jump; jump distance; jump distance graph

UR - http://eudml.org/doc/270366

ER -

## References

top- [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. Zbl0753.05067
- [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. Zbl0716.05028
- [4] G. Chartrand, F. Saba and H-B Zou, Edge rotations and distance between graphs, asopis Pst. Mat. 110 (1985) 87-91. Zbl0567.05044
- [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. Zbl0802.05035
- [6] E.B. Jarrett, Edge rotation and edge slide distance graphs, Computers and Mathematics with Applications, (to appear). Zbl0902.05021
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.