Distances between graphs under edge operations
type: Item
instance of: scholarly article
title: Distances between graphs under edge operations
zbMATH Open document ID: 0954.05026
DOI: 10.1016/0012-365X(95)00073-6
author: Wayne Goddard
author: H. C. Swart
published in: Discrete Mathematics
publication date: 2000-11-12T00:00:00Z
review text: There are several distances between isomorphism classes of graphs. In the paper under review three of them are treated, namely the edge move distance \(\delta_{\text{EM}}\) introduced by V. Balaz, J. Koca, V. Kvasnicka and M. Sekanina, the edge rotation distance \(\delta_{\text{ER}}\) introduced by G. Chartrand, F. Saba and H.-B. Zou, and the edge slide distance \(\delta_{\text{ES}}\) introduced by M. Johnson. Some bounds for them are found and the distances \(\delta_{\text{EM}}\) and \(\delta_{\text{ER}}\) are expressed by means of the so-called slot-shift. The influence of some graph operations on the distances is studied; the operations considered are adding an isolated vertex, taking two disjoint copies of the graph, and subdivision of each edge of the graph. Finally, \(\delta_{\text{ER}}\) on trees is studied.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1018477
zbMATH Keywords: distances
zbMATH Keywords: graph operations
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: A metric for graphs
cites work: On distances between isomorphism classes of graphs
cites work: Edge rotations and distance between graphs
cites work: Q3705253
cites work: Q3781777
cites work: On a certain distance between isomorphism classes of graphs
cites work: Q3674691
cites work: Comparison of various distances between isomorphism classes of graphs
cites work: Contraction distance between isomorphism classes of graphs
description: scientific article; zbMATH DE number 1018477