Results on the min-sum vertex cover problem

Abstract

Let G be a graph with the vertex set V (G), edge set E(G). A vertex labeling is a bijection f : V (G) _ {1, 2, . . . , |V (G)|}, and the weight of an edge e _ E(G) is given by g(e) = min{f(u), f(v)}. The min-sum vertex cover (msvc) is a vertex labeling that minimizes the vertex cover number ﾵs(G) = P e_E(G) g(e). The minimum such sum is called the msvc cost. In this paper, we give both general bounds and exact results for the msvc cost on several classes of graphs.