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.