On Graphlike k-Dissimilarity Vectors

Abstract

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