Covering a graph with cuts of minimum total size

A cut in a graph G is the set of all edges between some set of vertices S and its complement (S) over tilde = V(G) - S. A cut-cocer of G is a collection of cuts whose union is E(G) and the total size of a cut-cover is the sum of the number of edges of the cuts in the cover. The cut-cover size of a graph G, denoted by cs(G), is the minimum total size of a cut-cover of G. We give general bounds on cs(G), find sharp bounds for classes of graphs such as 4-colorable graphs and random graphs. We also address algorithmic aspects and give sharp bounds for the sum of the cut-cover sizes of a graph and its complement. We close with a list of open problems. (C) 2001 Elsevier Science B.V. All rights reserved.