k-Efficient partitions of graphs

A set S={u1,u2,…,ut} of vertices of G is an efficient dominating set if every vertex of G is dominated exactly once by the vertices of S. Letting Ui denote the set of vertices dominated by ui, we note that {U1,U2,…Ut} is a partition of the vertex set of G and that each Ui contains the vertex ui and all the vertices at distance~1 from it in G. In this paper, we generalize the concept of efficient domination by considering k-efficient domination partitions of the vertex set of G, where each element of the partition is a set consisting of a vertex ui and all the vertices at distance~di from it, where di∈{0,1,…,k}. For any integer k≥0, the k-efficient domination number of G equals the minimum order of a k-efficient partition of G. We determine bounds on the k-efficient domination number for general graphs, and for k∈{1,2}, we give exact values for some graph families. Complexity results are also obtained.