An Optimal Diagonal Tree Code

Abstract

It has been observed that not all the entries of $M( T )$, the distance matrix for a tree T, are necessary to determine T uniquely. For example, the submatrix of distances between end-vertices uniquely determines T. In this paper it is shown when T is canonically ordered, $2n - 3$ of the distances between the n end-vertices suffice for this determination. It is shown that $2n - 3$ is the minimum number of distances with this property. Linear algorithms for finding such a set of distances (encoding), given the tree, and for finding a tree (decoding), given the distances, are described.