Affordable Access

Access to the full text

Connected power domination in graphs

Authors
  • Brimkov, Boris1
  • Mikesell, Derek1
  • Smith, Logan1
  • 1 Rice University, Department of Computational and Applied Mathematics, Houston, TX, 77005, USA , Houston (United States)
Type
Published Article
Journal
Journal of Combinatorial Optimization
Publisher
Springer-Verlag
Publication Date
Jan 23, 2019
Volume
38
Issue
1
Pages
292–315
Identifiers
DOI: 10.1007/s10878-019-00380-7
Source
Springer Nature
Keywords
License
Yellow

Abstract

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 the connected power domination number of 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.

Report this publication

Statistics

Seen <100 times