Paul Dorbec ; Antonio González ; Claire Pennarun - Power domination in maximal planar graphs

dmtcs:5127 - Discrete Mathematics & Theoretical Computer Science, December 13, 2019, vol. 21 no. 4 - https://doi.org/10.23638/DMTCS-21-4-18
Power domination in maximal planar graphs

Authors: 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 .


Volume: vol. 21 no. 4
Section: Graph Theory
Published on: December 13, 2019
Submitted on: January 27, 2019
Keywords: propagation,power domination,maximal planar graph,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]


Share

Consultation statistics

This page has been seen 1224 times.
This article's PDF has been downloaded 189 times.