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 ${m_I}_{I in {{1,...,n} choose 2}}$ and ${M_I}_{I in {{1,...,n} choose 2}}$ be two families of positive real numbers parametrized by the $2$-subsets of $ {1,..., n}$ with $m_I leq M_I$ 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 $D_I ({cal G}) in [m_I, M_I] $ for any $I in {{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.

Weighted graphs with distances in given ranges / E. Rubei. - In: JOURNAL OF CLASSIFICATION. - ISSN 0176-4268. - STAMPA. - 33:(2016), pp. 282-297. [10.1007/s00357-016-9206-6]

Weighted graphs with distances in given ranges

RUBEI, ELENA
2016

Abstract

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 ${m_I}_{I in {{1,...,n} choose 2}}$ and ${M_I}_{I in {{1,...,n} choose 2}}$ be two families of positive real numbers parametrized by the $2$-subsets of $ {1,..., n}$ with $m_I leq M_I$ 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 $D_I ({cal G}) in [m_I, M_I] $ for any $I in {{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.
2016
33
282
297
Goal 11: Sustainable cities and communities
E. Rubei
File in questo prodotto:
File Dimensione Formato  
rangedist2.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 317.47 kB
Formato Adobe PDF
317.47 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/894758
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact