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