Efficient Domination in Graphs

In this chapter, we consider the concept of efficient domination, that is, the concept of dominating every vertex exactly once. An efficient dominating set S ⊆ V in a graph G = (V, E) is a dominating set with the additional property that the closed neighborhood N[v] of every vertex v ∈ V contains exactly one vertex in S. It should be noted at the outset that not every graph has an efficient dominating set, the cycles C4 and C5 being two small examples. Thus, the study of efficient domination in graphs focuses primarily on families of graphs each member of which has an efficient dominating set, and then algorithms for finding such sets, or on families of graphs for which it can be determined in polynomial time which members do and do not have efficient dominating sets.