Distances between graphs under edge operations (Q1356416): Difference between revisions

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.