Distances between graphs under edge operations
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.
scientific article; zbMATH DE number 1018477
scientific article