Edge rotation and edge slide distance graphs (Q1388979): Difference between revisions

An edge rotation (resp. slide) in a graph is the replacement of one vertex of an edge by another (resp. adjacent) one. For two graphs their \(r\)- (resp. \(s\)-) distance is the minimum number of edge rotations (resp. slides) necessary to transform one into the other. Pairs of graphs at \(r\)-distance \(m\) and \(s\)-distance \(n\) are constructed for any \(m\leq n\). An \(r\)- (resp. \(s\)-) distance graph is a set of graphs connected by all edges representing an edge rotation (resp. slide). Every graph is known to be isomorphic to some \(s\)-distance graph, while the same is conjectured for \(r\)-distance graphs. It is shown that all complete graphs, trees, cycles, wheels and complete bipartite graphs are \(r\)-distance graphs.