×

Edge rotation and edge slide distance graphs. (English) Zbl 0902.05021

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.

MSC:

05C12 Distance in graphs
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benadé, G.; Goddard, W.; McKee, T. A.; Winter, P. A., On distances between isomorphism classes of graphs, Math. Bohem., 116, 160-169 (1991) · Zbl 0753.05067
[2] Chartrand, G.; Saba, F.; Zou, H. B., Edge rotations and distance between graphs, C̆asopis Pĕst. Mat., 110, 87-91 (1985) · Zbl 0567.05044
[3] Johnson, M. A., An ordering of some metrics defined on the space of graphs, Czech. Math. J., 37, 75-85 (1987) · Zbl 0641.05027
[4] Chartrand, G.; Goddard, W.; Henning, M. A.; Lesniak, L.; Swart, H.; Wall, C. E., Which graphs are distance graphs, Ars Combin., 29A, 225-232 (1990) · Zbl 0716.05028
[5] Faudree, R. J.; Schelp, R. H.; Lesniak, L.; Gyárfár, A.; Lehel, J., On the rotation distance of graphs, Discrete Math., 126, 121-135 (1994) · Zbl 0802.05035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.