Power domination in maximal planar graphs
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4
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 .
@article{DMTCS_2019_21_4_a18,
author = {Dorbec, Paul and Gonz\'alez, Antonio and Pennarun, Claire},
title = {Power domination in maximal planar graphs},
journal = {Discrete mathematics & theoretical computer science},
year = {2019},
volume = {21},
number = {4},
doi = {10.23638/DMTCS-21-4-18},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-18/}
}
TY - JOUR AU - Dorbec, Paul AU - González, Antonio AU - Pennarun, Claire TI - Power domination in maximal planar graphs JO - Discrete mathematics & theoretical computer science PY - 2019 VL - 21 IS - 4 UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-18/ DO - 10.23638/DMTCS-21-4-18 LA - en ID - DMTCS_2019_21_4_a18 ER -
%0 Journal Article %A Dorbec, Paul %A González, Antonio %A Pennarun, Claire %T Power domination in maximal planar graphs %J Discrete mathematics & theoretical computer science %D 2019 %V 21 %N 4 %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-18/ %R 10.23638/DMTCS-21-4-18 %G en %F DMTCS_2019_21_4_a18
Dorbec, Paul; González, Antonio; Pennarun, Claire. Power domination in maximal planar graphs. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi: 10.23638/DMTCS-21-4-18
Cité par Sources :