Buneman's theorem for trees with exactly n vertices
Agnese Baldisserri · Florence Research (University of Florence) · 2014
Let ${\\cal T}=(T,w)$ be a positive-weighted tree with at least $n$ vertices. For any $i,j \\in \\{1,...,n\\}$, let $D_{i,j} ({\\cal T})$ be the weight of the unique path in $T$ connecting $i$ and $j$. The $D_{i,j} ({\\cal T})$ are called $2$-weights of ${\\cal T}$ and, if we put in order the $2$-weights, the vector which has the $D_{i,j} ({\\cal T})$ as components is called \\emph{$2$-dissimilarity vector} of $ {\\cal T}$. Given a family of positive real numbers $\\{D_{i,j}\\}_{i,j \\in \\{1,...,n\\}}$, we say that a positive-weighted tree ${\\cal T}=(T,w)$ realizes the family if $\\{1,...,n\\} \\subset V(T)$ and $D_{i,j}({\\cal T})=D_{i,j}$ for any $ i,j \\in \\{1,...,n\\}$. A characterization of $2$-dissimilarity families of positive weighted trees is already known (see \\cite{B}, \\cite{SimP} or \\cite{St}): the families must satisfy the well-known \\emph{four-point condition}. However we can wonder when there exists a positive-weighted tree with \\emph{exactly} $n$ vertices, $1,...,n,$ and realizing the family $\\{D_{i,j}\\}$. In this paper we will show that the four-point condition is necessary but no more sufficient, and so we will introduce two additional conditions.