Weighted Graphs with Distances in Given Ranges

Let G $$ \mathcal{G} $$ = (G,w) be a weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of the edges of G to the set of 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, j vertices of G, we define D {i,j}( G $$ \mathcal{G} $$ ) to be the minimum of the weights of the simple paths of G joining i and j. The D {i,j}( G $$ \mathcal{G} $$ ) are called 2-weights of G $$ \mathcal{G} $$ . Weighted graphs and their reconstruction from 2-weights have applications in several disciplines, such as biology and psychology. Let m I I ∈ 1 … n 2 $$ {\left\{{m}_I\right\}}_{I\in \left(\frac{\left\{1,\dots, n\right\}}{2}\right)} $$ and M I I ∈ 1 … n 2 $$ {\left\{{M}_I\right\}}_{I\in \left(\frac{\left\{1,\dots, n\right\}}{2}\right)} $$ be two families of positive real numbers parametrized by the 2-subsets of {1, …, n} with m I ≤ M I for any I; we study when there exist a positive-weighted graph G and an n-subset {1, …, n} of the set of its vertices such that D I ( G $$ \mathcal{G} $$ ) ∈ [m I ,M I ] for any I ∈ 1 … n 2 $$ I\in \left(\frac{\left\{1,\dots, n\right\}}{2}\right) $$ . Then we study the analogous problem for trees, both in the case of positive weights and in the case of general weights.