Weighted graphs with distances in given ranges

Abstract: Let

c a l 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} (c a l G)

to be the minimum of the weights of the simple paths of

G

joining

i

and

j

. The

D_{i, j} (c a l G)

are called

2

-weights of

c a l G

. Let

{m_{I}}_{I i n 1, ..., n c h o o s e 2}

and

{M_{I}}_{I i n 1, ..., n c h o o s e 2}

be two families of positive real numbers parametrized by the

2

-subsets of

1, ..., n

with

m_{I} l e q M_{I}

for any

I

; we study when there exist a positive-weighted graph

c a l G

and an

n

-subset

1, ..., n

of the set of its vertices such that

D_{I} (c a l G) i n [m_{I}, M_{I}]

for any

I i n 1, ..., n c h o o s e 2

. Then we study the analogous problem for trees, both in the case of positive weights and in the case of general weights.

Cites Work

Cited In (5)

This page was built for publication: Weighted graphs with distances in given ranges