EFFICIENT SETS IN GRAPHS

The efficiency of a set S of vertices in an undirected graph G=(V,E) i s defined to be epsilon(S)=\{v\v is-an-element-of V-S and v is adjacen t to exactly one vertex in S}/, i.e., the number of vertices in V-S th at are dominated by exactly one vertex in S. The efficiency of a graph G=(V,E) equals the maximum efficiency of any subset S of vertices of V. A linear time algorithm is presented for computing the efficiency o f an arbitrary tree and an NP-completeness proof is given for the prob lem of deciding if an arbitrary planar bipartite graph has a set S suc h that epsilon(S) greater-than-or-equal-to k, for some positive intege r k.