Power domination in maximal planar graphs

DOI10.23638/DMTCS-21-4-18MaRDI QIDQ5115466zbMATH OpenOpenAlexFDO

Authors

Publication date 13 August 2020

Full work available at URL https://arxiv.org/abs/1706.10047

propagation maximal planar graph power domination

Applications of graph theory (05C90) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: 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

g e

6 admits a power dominating set of size at most (n--2)/4 .

Recommendations

Cited in

(5)

This page was built for publication: Power domination in maximal planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115466)