zbMATH — the first resource for mathematics

Distances between rooted trees. (English) Zbl 0743.05019
The distance $$\delta_ T((T_ 1,r_ 1)$$, $$(T_ 2,r_ 2))$$ between $$n$$-vertex rooted trees $$T_ 1$$ with root $$r_ 1$$ and $$T_ 2$$ with root $$r_ 2$$ is $$n$$ minus the maximum number of vertices in a rooted subtree which is isomorphic to a rooted subtree in $$(T_ 1,r_ 1)$$ and in $$(T_ 2,r_ 2)$$. The distance $$\delta_ R((T_ 1,r_ 1)$$, $$(T_ 2,r_ 2))$$ is the maximum number of edge rotations between these rooted trees to transform $$(T_ 1,r_ 1)$$ into a rooted tree isomorphic to $$(T_ 2,r_ 2)$$. The author shows that these two distances are valid metrics and obtains various bounds on the distances. The maximum distance $$\delta_ T((T,r_ 1)$$, $$(T,r_ 2))$$, where $$r_ 1$$ and $$r_ 2$$ are any two vertices of $$T$$, is called the subtree elongation of $$T$$ and denoted $$\varepsilon_ T(T)$$; $$\varepsilon_ R(T)$$ is defined similarly. Bounds on $$\varepsilon_ T(T)$$ and $$\varepsilon_ R(T)$$ are given.
MSC:
 05C05 Trees 05C12 Distance in graphs
rooted trees
Full Text: