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 = V (G) \Gamma S. A cut-cover 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 will give general bounds on cs(G), find sharp bounds for classes of graphs such as 4-colorable graphs and random graphs and prove a Nordhaus-Gaddum type result. We close with a list of open problems