𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the rotation distance of graphs

✍ Scribed by R.J. Faudree; R.H. Schelp; L. Lesniak; A. Gyárfás; J. Lehel

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
972 KB
Volume
126
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let (x,y) be an edge of a graph G. Then the rotation of (x, y) about x is the operation of removing (x, y) from G and inserting (x, y') as an edge, where y' is a vertex of G. The rotation distance between graphs G and H is the minimum number of rotations necessary to transform G into H. Lower and upper bounds are given on the rotation distance of two graphs in terms of their greatest common subgraphs and their partial rotation link of largest cardinality. We also propose some extremal problems for the rotation distance of trees.

📜 SIMILAR VOLUMES

On the editing distance of graphs
On the editing distance of graphs
✍ Maria Axenovich; André Kézdy; Ryan Martin 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 2 views

## Abstract An edge‐operation on a graph __G__ is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs $\cal G$, the editing distance from __G__ to $\cal G$ is the smallest number of edge‐operations needed to modify __G__ into a graph

On the distance connectivity of graphs a
On the distance connectivity of graphs and digraphs
✍ M.A. Fiol; J. Fàbrega 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 475 KB

Let G=( V, E) be a digraph with diameter D # 1. For a given integer 1 t. The t-distance edge-connectivity of G is defined analogously. This paper studies some results on the distance connectivities of digraphs and bipartite digraphs. These results are given in terms of the parameter I, which can be

On the chromatic number of special dista
On the chromatic number of special distance graphs
✍ M. Voigt; H. Walther 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 153 KB

## A b&act Voigt, M. and H. Walther, On the chromatic number of special distance graphs, Discrete Mathematics 97 (1991) 395-397. For all 12 10 and u 2 1' -61+ 3 the chromatic number is proved to be 3 for distance graphs with all integers as vertices, and edges only if the vertices are at distance

On the distance matrix of a directed gra
On the distance matrix of a directed graph
✍ R. L. Graham; A. J. Hoffman; H. Hosoya 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

## Abstract In this note, we show how the determinant of the distance matrix __D(G__) of a weighted, directed graph __G__ can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks __G~i~__ of __G__. In particular, when cof __D(G__), the sum of the cofactors of _

Connectivity of distance graphs
Connectivity of distance graphs
✍ J.D. Currie 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 243 KB

Currie, J.D., Connectivity of distance graphs, Discrete Mathematics 103 (1992) 91-94. The author shows the following: Let K 2 Q be a H-module. Let G be a graph with vertex set V, a K-space. Suppose that edges of G are preserved under translations in V. Then if G has more than one connected componen