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 ().