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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-11232 |
| Date | 01 June 2019 |
| Creators | Chellali, Mustapha, Haynes, Teresa W., Hedetniemi, Stephen T. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | ETSU Faculty Works |
| Rights | http://creativecommons.org/licenses/by-sa/4.0/ |
Page generated in 0.0017 seconds