| Title |
|
On the Power Domination Number of de Bruijn and Kautz Digraphs |
|
|
| Publication Date |
|
| Author(s) |
|
| Editor |
|
Editor(s): Ljiljana Brankovic, Joe Ryan and William F Smyth |
|
|
| Type of document |
|
| Language |
|
| Entity Type |
|
| Publisher |
|
| Place of publication |
|
| Series |
|
Lecture Notes in Computer Science |
|
|
| DOI |
|
10.1007/978-3-319-78825-8_22 |
|
|
| UNE publication id |
|
| Abstract |
|
Let G=(V,A) be a directed graph, and let S⊆V be a set of vertices. Let the sequence S=S₀⊆S₁⊆S₂⊆⋯ be defined as follows: S₁ is obtained from S₀ by adding all out-neighbors of vertices in S₀. For k⩾2, Sₖ is obtained from Sₖ₋₁ by adding all vertices w such that for some vertex v∈Sₖ₋₁, w is the unique out-neighbor of v in V∖Sₖ₋₁. We set M(S)=S₀∪S₁∪⋯, and call S a power dominating set for G if M(S)=V(G). The minimum cardinality of such a set is called the power domination number of G. In this paper, we determine the power domination numbers of de Bruijn and Kautz digraphs. |
|
|
| Link |
|
| Citation |
|
Combinatorial Algorithms, v.10765, p. 264-272 |
|
|
| ISBN |
|
| Start page |
|
| End page |
|