{"docId":5967,"paperId":5127,"url":"https:\/\/dmtcs.episciences.org\/5127","doi":"10.23638\/DMTCS-21-4-18","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":373,"name":"vol. 21 no. 4"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01550353","repositoryVersion":3,"repositoryLink":"https:\/\/hal.science\/hal-01550353v3","dateSubmitted":"2019-01-27 11:39:07","dateAccepted":"2019-12-13 16:01:40","datePublished":"2019-12-13 16:01:55","titles":{"en":"Power domination in maximal planar graphs"},"authors":["Dorbec, Paul","Gonz\u00e1lez, Antonio","Pennarun, Claire"],"abstracts":{"en":"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 \u2265 6 admits a power dominating set of size at most (n\u22122)\/4 ."},"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]"]}