We consider several extremal problems in graph theory and computational geometry.A cut in a graph G is the set of all edges between some set of vertices S and its complement V(G)-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 give general bounds on cs(G), find sharp bounds for classes of graphs such as 4-colorable graphs and random graphs. We give sharp bounds for the sum of the cut-cover sizes of a graph and its complement. We also determine the cut-cover size of the complete graph on n vertices and establish a close connection between this problem and an isoperimetric problem due to Ahlswede and Katona.
Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Each interior wall has an arbitrarily placed, arbitrarily small doorway. We determine the minimum number of guards that suffice to guard all art galleries with n vertices and m interior walls. We also determine the minimum number of guards that suffice for galleries with convex rooms of specified minimum size. The proofs lead to linear time guard placement algorithms in most cases.
What is the maximum number of edges in a multigraph on n vertices if every k-set spans at most r edges? We asymptotically determine this maximum for almost all k and r as n tends to infinity, thus giving a generalization of Turán's theorem. We find exact answers in many cases, even when edges of negative multiplicity are allowed.