Weighted Graphs with Distances in Given Ranges
Elena Rubei ()
Additional contact information
Elena Rubei: University of Florence;
Journal of Classification, 2016, vol. 33, issue 2, No 7, 282-297
Abstract:
Abstract 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.
Keywords: Weighted graphs; Distances; Range (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)
Downloads: (external link)
http://link.springer.com/10.1007/s00357-016-9206-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:spr:jclass:v:33:y:2016:i:2:d:10.1007_s00357-016-9206-6
Ordering information: This journal article can be ordered from
http://www.springer. ... hods/journal/357/PS2
DOI: 10.1007/s00357-016-9206-6
Access Statistics for this article
Journal of Classification is currently edited by Douglas Steinley
More articles in Journal of Classification from Springer, The Classification Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().