BZPEER

preprint2016arXiv

A characterization of dissimilarity families of trees

Let ${\cal T}=(T,w)$ be a weighted finite tree with leaves $1,..., n$ .For any $I :=\{i_1,..., i_k \} \subset \{1,...,n\}$ , let $D_I ({\cal T})$ be the weight of the minimal subtree of $T$ connecting $i_1,..., i_k$ ; the $D_{I} ({\cal T})$ are called $k$ -weights of ${\cal T}$ . Given a family of real numbers parametrized by the $k$ -subsets of $\{1,..., n\}$ , $\{D_I\}_{I \in {\{1,...,n\} \choose k}}$ , we say that a weighted tree ${\cal T}=(T,w)$ with leaves $1,..., n$ realizes the family if $D_I({\cal T})=D_I$ for any $I$ . In 2006 Levy, Yoshida and Pachter defined, for any positive-weighted tree ${\cal T}=(T,w)$ with $\{1,..., n\}$ as leaf set and any $i, j \in \{1,..., n\}$ , the numbers $S_{i,j}$ to be $\sum_{Y \in {\{1,..., n\} -\{i,j\} \choose k-2}} D_{i,j ,Y}({\cal T})$ ; they proved that there exists a positive-weighted tree ${\cal T}' =(T',w')$ such that $D_{i,j}({\cal T}')=S_{i,j}$ for any $i,j \in \{1,..., n\}$ and that this new tree is, in some way, similar to the given one. In this paper, by using the $S_{i,j}$ defined by Levy, Yoshida and Pachter, we characterize families of real numbers parametrized by ${\{1,...,n\} \choose k}$ that are the families of $k$ -weights of weighted trees with leaf set equal to $\{1,...., n\}$ and weights of the internal edges positive.

preprint2016arXiv

Families of $2$ -weights of some particular graphs

Let ${\cal G}=(G,w)$ be a positive-weighted graph, that is a graph $G$ endowed with a function $w$ from the edge set of $G$ to the set of positive real numbers; for any distinct vertices $i,j$ , we define $D_{i,j}({\cal G})$ to be the weight of the path in $G$ joining $i$ and $j$ with minimum weight. In this paper we fix a particular class of graphs and we give a criterion to establish whether, given a family of positive real numbers $\{D_I\}_{I \in { \{1,...., n\} \choose 2}}$ , there exists a positive-weighted graph ${\cal G} =(G,w)$ in the class we have fixed, with vertex set equal to $\{1,....,n\}$ and such that $D_I ({\cal G}) =D_I$ for any $I \in { \{1,...., n\} \choose 2}$ . In particular, the classes of graphs we consider are the following: snakes, caterpillars, polygons, bipartite graphs, complete graphs, planar graphs.

preprint2016arXiv

Graphlike families of multiweights

Let ${\cal G}=(G,w)$ be a weighted graph , that is, a graph $G$ endowed with a function $w$ from the edge set of $G$ to the set of real numbers; for any subset $S$ of the vertex set of $G$ , we define $D_S({\cal G})$ to be the minimum of the weights of the subgraphs of $G$ whose vertex set contains $S$ ; we call $D_S({\cal G})$ a multiweight of ${\cal G}$ . Let $X$ be a finite set and let $\{D_S\}_{S \subset X, \; \sharp S \geq 2}$ be a family of positive real numbers. We find necessary and sufficient conditions for the family to be the family of multiweights of a positive-weighted graph with vertex set $X$ . Moreover we study the analogous problem for trees. Finally, we find a criterion to say if there exists a nonnegative-weighted tree ${\cal T}$ with leaf set $X$ and such that $D_S ({\cal T})=D_S$ for any $S \subset X$ .

preprint2015arXiv

Families of multiweights and pseudostars

Let ${\cal T}=(T,w)$ be a weighted finite tree with leaves $1,..., n$ .For any $I :=\{i_1,..., i_k \} \subset \{1,...,n\}$ ,let $D_I ({\cal T})$ be the weight of the minimal subtree of $T$ connecting $i_1,..., i_k$ ; the $D_{I} ({\cal T})$ are called $k$ -weights of ${\cal T}$ . Given a family of real numbers parametrized by the $k$ -subsets of $\{1,..., n\}$ , $\{D_I\}_{I \in {\{1,...,n\} \choose k}}$ , we say that a weighted tree ${\cal T}=(T,w)$ with leaves $1,..., n$ realizes the family if $D_I({\cal T})=D_I$ for any $I$ . In [P-S] Pachter and Speyer proved that, if $3 \leq k \leq (n+1)/2$ and $\{D_I\}_{I \in {\{1,...,n\} \choose k}}$ is a family of positive real numbers, then there exists at most one positive-weighted essential tree ${\cal T}$ with leaves $1,...,n$ that realizes the family (where "essential" means that there are no vertices of degree $2$ ). We say that a tree $P$ is a pseudostar of kind $(n,k)$ if the cardinality of the leaf set is $n$ and any edge of $P$ divides the leaf set into two sets such that at least one of them has cardinality $\geq k$ . Here we show that, if $3 \leq k \leq n-1$ and $\{D_I\}_{I \in {\{1,...,n\} \choose k}}$ is a family of real numbers realized by some weighted tree, then there is exactly one weighted essential pseudostar ${\cal P}=(P,w)$ of kind $(n,k)$ with leaves $1,...,n$ and without internal edges of weight $0$ , that realizes the family; moreover we describe how any other weighted tree realizing the family can be obtained from ${\cal P}$ . Finally we examine the range of the total weight of the weighted trees realizing a fixed family.

preprint2015arXiv

Treelike families of multiweights

Let ${\cal T}=(T,w)$ be a weighted finite tree with leaves $1,..., n$ . For any $I :=\{i_1,..., i_k \} \subset \{1,...,n\}$ , let $D_I ({\cal T})$ be the weight of the minimal subtree of $T$ connecting $i_1,..., i_k$ ; the $D_{I} ({\cal T})$ are called $k$ -weights of ${\cal T}$ . Given a family of real numbers parametrized by the $k$ -subsets of $\{1,..., n\}$ , $\{D_I\}_{I \in {\{1,...,n\} \choose k}}$ , we say that a weighted tree ${\cal T}=(T,w)$ with leaves $1,..., n$ realizes the family if $D_I({\cal T})=D_I$ for any $I$ . We give a characterization of the families of real numbers that are realized by some weighted tree.

preprint2014arXiv

Buneman's theorem for trees with exatcly n vertices

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 (see Theorem \ref{thm:ThmAgne}).

preprint2013arXiv

On graphlike k-dissimilarity vectors

Let {\cal G}=(G,w) be a positive-weighted simple finite graph, that is, let G be a simple finite graph endowed with a function w from the set of the edges of G to the set of the positive real numbers. For any subgraph G' of G, we define w(G') to be the sum of the weights of the edges of G'. For any i_1,..., i_k vertices of G, let D_{i_1,.... i_k}({\cal G}) be the minimum of the weights of the subgraphs of G connecting i_1,..., i_k. The D_{i_1,.... i_k}({\cal G}) are called k-weights of {\cal G}. Given a family of positive real numbers parametrized by the k-subsets of {1,..., n}, {D_I}_{I k-subset of {1,...,n}}, we can wonder when there exist a weighted graph {\cal G} (or a weighted tree) and an n-subset {1,..., n} of the set of its vertices such that D_I({\cal G}) =D_I for any I k-subset of {1,...,n}. In this paper we study this problem in the case k=n-1.

Agnese Baldisserri

Research overview

Is this your work?

7 publications

A characterization of dissimilarity families of trees

Families of $2$ -weights of some particular graphs

Graphlike families of multiweights

Families of multiweights and pseudostars

Treelike families of multiweights

Buneman's theorem for trees with exatcly n vertices

On graphlike k-dissimilarity vectors

See the researcher in context

Building this map preview

Agnese Baldisserri

Research overview

Is this your work?

7 publications

A characterization of dissimilarity families of trees

Families of 222-weights of some particular graphs

Graphlike families of multiweights

Families of multiweights and pseudostars

Treelike families of multiweights

Buneman's theorem for trees with exatcly n vertices

On graphlike k-dissimilarity vectors

See the researcher in context

Building this map preview

Families of $2$ -weights of some particular graphs