@article {
author = {Chellali, M and Haynes, Teresa W. and Hedetniemi, Stephen T.},
title = {k-Efficient partitions of graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {109-122},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26446.1112},
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 = {domination,Efficient Domination,Distance-$k$ domination},
url = {https://comb-opt.azaruniv.ac.ir/article_13852.html},
eprint = {https://comb-opt.azaruniv.ac.ir/article_13852_478f6dfde08ed596744a7773348bc29a.pdf}
}