Menu
A vertex set \(S \subseteq V(G)\) is a perfect code or efficient dominating set for a graph \(G\) if each vertex of \(G\) is dominated by \(S\) exactly once. Not every graph has an efficient dominating set, and the efficient domination number \(F(G)\) is the maximum number of vertices one can dominate given that no vertex is dominated more than once. That is, \(F(G)\) is the maximum influence of a packing \(S \subseteq V(G)\). In this paper, we begin the study of \(LF(G)\), the lower efficient domination number of \(G\), which is the minimum number of vertices dominated by a maximal packing. We show that the decision problem associated with deciding if \(LF(G) \leq K\) is an NP-complete problem. The principal result is a characterization of trees \(T\) where \(LF(T) = F(T)\).