On Efficient Construction of MinimumSum Vertex Covers
Abstract
Let G = ( V, E) be a simple graph. A vertex labeling is a bijection f: V → { l, 2, ... ,!VI}. The
weight w(e) of an edge e = uv ∈E is given by w(e) = min{f(u), f(v)}. The minimumsum ver~ex
cover is a vertex labeling that minimizes ∑ₑ∈ ᴇ ʷ(ͤ) . The minimum such sum is called the min~mumsum
vertex cover cost, denoted by µ (G). The problem of determining µs (G) is NPcomplete
m the general case, however, we show that minimumsum vertex covers of split graphs and caterpillars
can be computed in polynomial time.
Collections
Related items
Showing items related by title, author, creator and subject.

Results on the minsum vertex cover problem
Gera, Ralucca; Rasmussen, Craig W.; Stanica, Pantelimon; Horton, Steve (2006);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 minsum vertex ... 
Realizable triples in dominator colorings
Fletcher, Douglas M. (Monterey, California. Naval Postgraduate School, 200706);Given a graph G and its vertex set V(G), the chromatic number, Chi(G), represents the minimum number of colors required to color the vertices of G so that no two adjacent vertices have the same color. The domination number ... 
Stratified domination in oriented graphs
Gera, Ralucca; Ping, Zhang (2007);An oriented graph is 2stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let H be a 2stratified oriented graph ...