Chellali, M., Haynes, T., Hedetniemi, S. (2019). $k$-Efficient partitions of graphs. Communications in Combinatorics and Optimization, (), -. doi: 10.22049/cco.2019.26446.1112

M Chellali; Teresa W. Haynes; Stephen T. Hedetniemi. "$k$-Efficient partitions of graphs". Communications in Combinatorics and Optimization, , , 2019, -. doi: 10.22049/cco.2019.26446.1112

Chellali, M., Haynes, T., Hedetniemi, S. (2019). '$k$-Efficient partitions of graphs', Communications in Combinatorics and Optimization, (), pp. -. doi: 10.22049/cco.2019.26446.1112

Chellali, M., Haynes, T., Hedetniemi, S. $k$-Efficient partitions of graphs. Communications in Combinatorics and Optimization, 2019; (): -. doi: 10.22049/cco.2019.26446.1112

^{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.