On some relations between 2-trees and tree metrics

A tree function (TF) t on a finite set X is a real function on the set of the pairs of elements of X satisfying the four-point condition: for all distinct x, y, z, w is an element of X, t(xy)+ t(zw)less than or equal to max(t(xz)+ t(yw), t(xw)+ t(yz)). Equivalently, t is representable by the lengths of the paths between the leaves of a valued tree T-l. TFs are a straightforward generalization of the tree dissimilarities and tree metrics of the literature. A graph Theta is a 2-tree if it belongs to the following class Q:: an edge-graph belongs to Q: if Theta' is an element of Q and yz is an edge of Theta', then the graph obtained by the addition to Theta' of a new vertex x adjacent to y and z belongs to Q. These graphs, and the more general k-trees, have been studied in the literature as generalizations of trees. It is first explicited here how to make a TF t(Theta,d) correspond to any positively valued 2-tree Od On X. Then, given a tree dissimilarity t, the set Q(t) of the 2-trees Theta such that t=t(Theta,t) is studied. Any element of Q(t) gives a way of summarizing t by its restriction to a minimal subset of entries. Several characterizations and properties of the elements of Q(t) are given. We describe five classes of such elements, including two new ones. Associated with a dissimilarity of the general type, these classes of 2-trees lead to methods for the recognition and fitting of tree dissimilarities.