# k-Efficient partitions of graphs

Document Type: Original paper

Authors

1 LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

2 Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN 37614-0002 USA

3 Professor Emeritus, School of Computing, Clemson University, Clemson, SC 29634 USA

Abstract

A set \$S = {u_1,u_2, ldots, u_t}\$ of vertices of \$G\$ is an efficient
dominating set if every vertex of \$G\$ is dominated exactly once by the
vertices of \$S\$. Letting \$U_i\$ denote the set of vertices dominated by \$u_i\$%
, we note that \${U_1, U_2, ldots U_t}\$ is a partition of the vertex set
of \$G\$ and that each \$U_i\$ contains the vertex \$u_i\$ 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 \$u_i\$ and all the vertices at distance~\$d_i\$ from it,
where \$d_i in {0,1, ldots, k}\$. For any integer \$k geq 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 in {1,2}\$, we give exact
values for some graph families. Complexity results are also obtained.

Keywords

Main Subjects