Closed neighborhood order dominating functions

The linear programmimg formulations of graph domination and graph packing are duals. Likewise, fractional efficient domination for a graph G has as its dual the parameter discussed in this paper, namely the minimum weight of a real-valued function f: V(G) → [0, ∞) such that the sum of the weights in each closed neighborhood is at least its cardinality. The fractional and integer "closed neighborhood order domination" parameters, W_f and W, are introduced. Deciding if W(G) ≤ k is an NPcomplete problem even for just the class of bipartite graphs or chordal graphs. A linear time algorithm for computing W(T) for an arbitrary tree T is presented. Other theoretical and computational results are presented.