Nordhaus–Gaddum problems for power domination

dc.contributor.author Benson, Katherine
dc.contributor.author Ferrero, Daniela
dc.contributor.author Flagg, Mary
dc.contributor.author Furst, Veronika
dc.contributor.author Hogben, Leslie
dc.contributor.author Vasilevska, Violeta
dc.contributor.department Electrical and Computer Engineering
dc.contributor.department Mathematics
dc.date 2019-06-25T14:27:55.000
dc.date.accessioned 2020-06-30T06:00:23Z
dc.date.available 2020-06-30T06:00:23Z
dc.date.copyright Mon Jan 01 00:00:00 UTC 2018
dc.date.embargo 2020-06-28
dc.date.issued 2018-12-31
dc.description.abstract <p>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.</p>
dc.description.comments <p>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." <em>Discrete Applied Mathematics</em> 251 (2018): 103-113. DOI: <a href="http://dx.doi.org/10.1016/j.dam.2018.06.004" target="_blank">10.1016/j.dam.2018.06.004</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/205/
dc.identifier.articleid 1206
dc.identifier.contextkey 14386782
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/205
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54596
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/205/2018_HogbenLeslie_NordhausGaddum.pdf|||Fri Jan 14 22:25:35 UTC 2022
dc.source.uri 10.1016/j.dam.2018.06.004
dc.subject.disciplines Applied Mathematics
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.keywords power domination
dc.subject.keywords domination
dc.subject.keywords zero forcing
dc.subject.keywords Nordhaus-Gaddum
dc.title Nordhaus–Gaddum problems for power domination
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication 0131698a-00df-41ad-8919-35fb630b282b
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
2018_HogbenLeslie_NordhausGaddum.pdf
Size:
378.92 KB
Format:
Adobe Portable Document Format
Description:
Collections