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 1; Antonio González 2; Claire Pennarun 3

  • 1 Université de Caen Normandie
  • 2 Department of Didactics of Mathematics, Faculty of Educational Sciences, Universidad de Sevilla
  • 3 Laboratoire Bordelais de Recherche en Informatique

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
Accepted on: October 27, 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]

Consultation statistics

This page has been seen 1374 times.
This article's PDF has been downloaded 277 times.