| Autor: |
Paul Dorbec, Antonio González, Claire Pennarun |
| Jazyk: |
angličtina |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
Discrete Mathematics & Theoretical Computer Science, Vol vol. 21 no. 4, Iss Graph Theory (2019) |
| Druh dokumentu: |
article |
| ISSN: |
1365-8050 |
| DOI: |
10.23638/DMTCS-21-4-18 |
| Popis: |
Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially the set S together with all its neighbors. Then iteratively, whenever some monitored vertex v has a single neighbor u not yet monitored, u gets monitored. A set S is said to be a power dominating set of the graph G if all vertices of G eventually are monitored. The power domination number of a graph is the minimum size of a power dominating set. In this paper, we prove that any maximal planar graph of order n ≥ 6 admits a power dominating set of size at most (n−2)/4 . |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
