Zelinka, Bohdan Distances between rooted trees. (English) Zbl 0743.05019 Math. Bohem. 116, No. 1, 101-107 (1991). 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. Reviewer: A.Tucker (Stony Brook) MSC: 05C05 Trees 05C12 Distance in graphs Keywords:rooted trees PDF BibTeX XML Cite \textit{B. Zelinka}, Math. Bohem. 116, No. 1, 101--107 (1991; Zbl 0743.05019) Full Text: EuDML