Power domination in maximal planar graphs
From MaRDI portal
Publication:5115466
DOI10.23638/DMTCS-21-4-18zbMATH Open1445.05077arXiv1706.10047OpenAlexW2996249744MaRDI QIDQ5115466FDOQ5115466
Authors:
Publication date: 13 August 2020
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 6 admits a power dominating set of size at most (n--2)/4 .
Full work available at URL: https://arxiv.org/abs/1706.10047
Recommendations
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)
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)
