Distances between rooted trees. (English) Zbl 0743.05019

Zelinka, Bohdan

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