Low-cost electrical monitoring: power-domination in triangulations

Claire Pennarun

LaBRI - CNRS, Univ. Bordeaux

Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. A vertex is *monitored* by a set of vertices $S$ if: $v$ is in $S$ or has a neighbor in $S$, or one monitored neighbor $u$ of $v$ has all its neighbors monitored except for $v$. Given a graph $G$, a set $S \in V(G)$ is said to be power dominating if all vertices of $G$ are monitored by it. The goal is then to find a power dominating set $S$ of minimum size for a given graph. We present an algorithm producing a power dominating set of order at most $\dfrac{n-2}{4}$ for any maximal planar graph of order $n \geq 6$.