$k$-Efficient partitions of graphs
| Autor: | M. Chellali, Teresa W. Haynes, Stephen T. Hedetniemi |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Communications in Combinatorics and Optimization, Vol 4, Iss 2, Pp 109-122 (2019) |
| Druh dokumentu: | article |
| ISSN: | 2538-2128 2538-2136 |
| DOI: | 10.22049/CCO.2019.26446.1112 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|