- Title
- On the power domination number of de Bruijn and Kautz digraphs
- Creator
- Grigorious, Cyraic; Kalinowski, Thomas; Stephen, Sudeep
- Relation
- 28th International Workshop on Combinatorial Algorithms (IWOCA 2017). Combinatorial Algorithms 28th International Workshop, IWOCA 2017: Revised Selected Papers (Newcastle, NSW 17-21 July, 2017) p. 264-272
- Publisher Link
- http://dx.doi.org/10.1007/978-3-319-78825-8_22
- Publisher
- Springer International Publishing
- Resource Type
- conference paper
- Date
- 2018
- Description
- Let G=(V,A) be a directed graph, and let S⊆V be a set of vertices. Let the sequence S=S0⊆S1⊆S2⊆⋯ be defined as follows: S1 is obtained from S0 by adding all out-neighbors of vertices in S0. For k⩾2, Sk is obtained from Sk−1 by adding all vertices w such that for some vertex v∈Sk−1, w is the unique out-neighbor of v in V∖Sk−1. We set M(S)=S0∪S1∪⋯, 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.
- Subject
- power domination; de Bruijn digraph; Kautz diagraph
- Identifier
- http://hdl.handle.net/1959.13/1421771
- Identifier
- uon:37764
- Identifier
- ISBN:9783319788258
- Language
- eng
- Full Text
- Reviewed
- Hits: 1446
- Visitors: 1743
- Downloads: 305
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 235 KB | Adobe Acrobat PDF | View Details Download |