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.
05C05 Trees
05C12 Distance in graphs
rooted trees
Full Text: EuDML