Covering a graph with cuts of minimum total size (Q5939921)

A cut in a graph \(G\) is the set of all edges between some set \(S\) of vertices of \(G\) and its complement \(\overline S\) in \(V(G)\). A cut-cover of \(G\) is a collection of cuts covering all edges of \(G\), its size is the sum of the cardinalities of the cuts, and the cut-cover size \(\text{cs}(G)\) of \(G\) is the minimum size of a cut-cover of \(G\). General bounds on \(\text{cs}(G)\) are given, for instance \(2e(G)- \text{Cut}(G)\leq \text{cs}(G)\leq 2e(G)- \text{Cut}'(G)\) (where \(\text{Cut}(G)\) resp. \(\text{Cut}'(G)\) denotes the maximal cardinality of an arbitrary cut resp. of a cut defined by a stable set of vertices) and another one of Nordhaus-Gaddum type combining \(\text{cs}(G)\) and \(\text{cs}(\overline G)\). Precise values of \(\text{cs}(G)\) for special graphs are given as well as sharp bounds for classes of graphs such as 4-colorable graphs. While in general the problem of determining \(\text{cs}(G)\) is NP-complete, \(\text{cs}(G)\) of planar graphs can be found in polynomial time. Connections of \(\text{cs}(G)\) are drawn to a geometric representation of \(G\) and to the bandwidth-sum of \(G\).