Metrization of weighted graphs

Details Metrization of weighted graphs Metrization of weighted graphs

2011-05-31

arxiv.org/abs/1105.6167v1

Mathematics

Combinatorics

7 figures

Scientific paper

We find a set of necessary and sufficient conditions under which the weight $w:E\to\mathbb R^+$ on the graph $G=(V,E)$ can be extended to a pseudometric $d:V\times V\to\mathbb R^+$. If these conditions hold and $G$ is a connected graph, then the set $\mathfrak M_w$ of all such extensions is nonvoid and the shortest-path pseudometric $d_w$ is the greatest element of $\mathfrak M_w$ with respect to the partial ordering $d_1 \leqslant d_2$ if and only if $d_1(u,v) \leqslant d_2(u,v)$ for all $u,v\in V$. It is shown that every nonvoid poset $(\mathfrak M_w,\leqslant)$ contains the least element $\rho_{0,w}$ if and only if $G$ is a complete $k$-partite graph with $k\geqslant 2$ and in this case the explicit formula for computation of $\rho_{0,w}$ is obtained.

Affiliated with

Also associated with

No associations

Rating

Metrization of weighted graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Metrization of weighted graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Metrization of weighted graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-337687