Connected power domination in graphs
Connected power domination in graphs
复制标题
DOI：
10.1007/s10878-019-00380-7
复制
发表时间：
2017-12
影响因子：
1
通讯作者：
Boris Brimkov;Derek Mikesell;Logan A. Smith
中科院分区：
文献类型：
--
作者：
Boris Brimkov;Derek Mikesell;Logan A. Smith
图中功率支配的研究源于在电网中放置最少数量的测量设备同时监控整个网络的问题。图的功率支配集是一组顶点，从这些顶点可以观察到图中的每个顶点，遵循一组用于电力系统监控的规则。在本文中，我们研究了寻找最小幂控制集的连通问题；这种集合的基数称为图的连通幂支配数。我们证明了图的连通幂控制数在一般情况下是np困难的，但在仙人掌图和块图中可以在线性时间内计算出来。我们还给出了关于连接功率控制的各种结构结果，包括切顶点分解和各种顶点和边缘操作对连接功率控制数的影响的表征。最后，我们提出了功率控制、连接功率控制和功率传播时间的新的整数规划公式，并给出了计算结果。
The study of power domination in graphs arises from the problem of placing a minimum number of measurement devices in an electrical network while monitoring the entire network. A power dominating set of a graph is a set of vertices from which every vertex in the graph can be observed, following a set of rules for power system monitoring. In this paper, we study the problem of finding a minimum power dominating set which is connected; the cardinality of such a set is called theconnected power domination numberof the graph. We show that the connected power domination number of a graph is NP-hard to compute in general, but can be computed in linear time in cactus graphs and block graphs. We also give various structural results about connected power domination, including a cut vertex decomposition and a characterization of the effects of various vertex and edge operations on the connected power domination number. Finally, we present novel integer programming formulations for power domination, connected power domination, and power propagation time, and give computational results.