Lightweight paths in graphs

Abstract

Let $k$ be a positive integer, $G$ be a graph on $V(G)$ containing a path on $k$ vertices, and w be a weight function assigning each vertex $v \in V(G)$ a real weight $w(v)$. Upper bounds on the weight $w(P)=\sum_{v\in V(P)}w(v)$ of $P$ are presented, where $P$ is chosen among all paths of $G$ on $k$ vertices with smallest weight.