episciences.org_5127_1675066532
1675066532
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
12
13
2019
vol. 21 no. 4
Graph Theory
Power domination in maximal planar graphs
Paul
Dorbec
Antonio
González
Claire
Pennarun
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 .
12
13
2019
5127
https://hal.science/hal01550353v3
https://hal.science/hal01550353v2
https://hal.science/hal01550353v1
10.23638/DMTCS21418
https://dmtcs.episciences.org/5127

https://dmtcs.episciences.org/5967/pdf

https://dmtcs.episciences.org/5967/pdf