2014/09/12 by Elena Rubei, Rubei, Elena
Computer Science · Mathematics · #05C05 #05C12 #05C22 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1409.3863
openalex publication_date 2014/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \cal 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\ (\cal G) to be the minimum of the weights of the simple paths of G joining i and j. The D_\i,j\ (\cal G) are called 2-weights of \cal G. Let \mI\_I ∈ \1,...,n\ \choose 2 and \MI\_I ∈ \1,...,n\ \choose 2 be two families of positive real numbers parametrized by the 2-subsets of \1,..., n\ with mI ≤ MI for any I; we study when there exist a positive-weighted graph \cal G and an n-subset \1,..., n\ of the set of its vertices such that DI (\cal G) ∈ [mI, MI] for any I ∈ \1,...,n\ \choose 2. Then we study the analogous problem for trees, both in the case of positive weights and in the case of general weights.