Campus Units

Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

12-31-2018

Journal or Book Title

Discrete Applied Mathematics

Volume

251

First Page

103

Last Page

113

DOI

10.1016/j.dam.2018.06.004

Abstract

A power dominating set of a graph G is a set S of vertices that can observe the entire graph under the rules that (1) the closed neighborhood of every vertex in S is observed, and (2) if a vertex and all but one of its neighbors are observed, then the remaining neighbor is observed; the second rule is applied iteratively. The power domination number of G, denoted by gamma p(G), is the minimum number of vertices in a power dominating set. A Nordhaus-Gaddum problem for power domination is to determine a tight lower or upper bound on gamma p(G) + gamma p(G) or gamma p(G).gamma p(G), where G denotes the complement of G. The upper and lower Nordhaus-Gaddum bounds over all graphs for the power domination number follow from known bounds on the domination number and examples. In this note we improve the upper sum bound for the power domination number substantially for graphs having the property that both the graph and its complement are connected. For these graphs, our bound is tight and is also significantly better than the corresponding bound for the domination number. We also improve the product upper bound for the power domination number for graphs with certain properties.

Comments

This is a manuscript of an article published as Benson, Katherine F., Daniela Ferrero, Mary Flagg, Veronika Furst, Leslie Hogben, and Violeta Vasilevska. "Nordhaus–Gaddum problems for power domination." Discrete Applied Mathematics 251 (2018): 103-113. DOI: 10.1016/j.dam.2018.06.004. Posted with permission.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier B.V.

Language

en

File Format

application/pdf

Available for download on Sunday, June 28, 2020

Published Version

Share

COinS