Weighted graphs with distances in given ranges

Original · EN

Let 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{ᵢ,ⱼ} (G) to be the minimum of the weights of the simple paths of G joining i and j. The D{ᵢ,ⱼ} (G) are called 2-weights of G. Let {mᵢ}I ∈ {1,...,n} 2 and {Mᵢ}I ∈ {1,...,n} 2 be two families of positive real numbers parametrized by the 2-subsets of {1,..., n} with mᵢ ≤ Mᵢ 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ᵢ (G) ∈ [mᵢ, Mᵢ] for any I ∈ {1,...,n} 2. Then we study the analogous problem for trees, both in the case of positive weights and in the case of general weights.