A vertex υ in a set S is said to be cost effective if it is adjacent to at least as many vertices in V\S as it is in S and is very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is (very) cost effective if every vertex in S is (very) cost effective. The minimum cardinality of a (very) cost effective dominating set of G is the (very) cost effective domination number of G. Our main results include a quadratic upper bound on the very cost effective domination number of a graph in terms of its domination number. The proof of this result gives a linear upper bound for hereditarily sparse graphs which include trees. We show that no such linear bound exists for graphs in general, even when restricted to bipartite graphs. Further, we characterize the extremal trees attaining the bound. Noting that the very cost effective domination number is bounded below by the domination number, we show that every value of the very cost effective domination number between these lower and upper bounds for trees is realizable. Similar results are given for the cost effective domination number.

For any integer k≥0, a set of vertices S of a graph G=(V,E) is k-cost-effective if for every v∈S,|N(v)∩(V∖S)|≥|N(v)∩S|+k. In this paper we study the minimum cardinality of a maximal k-cost-effective set and the maximum cardinality of a k-cost-effective set. We obtain Gallai-type results involving the k-cost-effective and global k-offensive alliance parameters, and we provide bounds on the maximum k-cost-effective number. Finally, we consider k-cost-effective sets that are also dominating. We show that computing the k-cost-effective domination number is NP-complete for bipartite graphs. Moreover, we note that not all trees have a k-cost-effective dominating set and give a constructive characterization of those that do.