×

Nordhaus-Gaddum problems for power domination. (English) Zbl 1401.05210

Summary: 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(\overline{G})\) or \(\gamma_P(G) \cdot \gamma_P(\overline{G})\), where \(\overline{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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barioli, F.; Barrett, W.; Butler, S.; Cioabă, S. M.; Cvetković, D.; Fallat, S. M.; Godsil, C.; Haemers, W.; Hogben, L.; Mikkelson, R.; Narayan, S.; Pryporova, O.; Sciriha, I.; So, W.; Stevanović, D.; van der Holst, H.; Vander Meulen, K.; Wangsness, A., Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428, 1628-1648, (2008) · Zbl 1135.05035
[2] Aouchiche, M.; Hansen, P., A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math., 161, 466-546, (2013) · Zbl 1259.05083
[3] Arumugam, S.; Paulraj Joseph, J., Domination in graphs, Int. J. Manag. Syst., 11, 177-182, (1995)
[4] Baldwin, T. L.; Mili, L.; Boisen, M. B.; Adapa, Jr. R., Power system observability with minimal phasor measurement placement, IEEE Trans. Power Syst., 8, 707-715, (1993)
[5] Benson, K. F.; Ferrero, D.; Flagg, M.; Furst, V.; Hogben, L.; Vasilevska, V.; Wissman, B., Zero forcing and power domination for graph products, Australas. J. Combin., 70, 221-235, (2018) · Zbl 1383.05225
[6] Brigham, R. C.; Chinn, P. Z.; Dutton, R. D., Vertex domination-critical graphs, Networks, 18, 173-179, (1988) · Zbl 0658.05042
[7] Burgarth, D.; Giovannetti, V., Full control by locally induced relaxation, Phys. Rev. Lett., PRL, 99, (2007)
[8] N. Dean, A. Ilic, I. Ramirez, J. Shen, K. Tian, On the power dominating sets of hypercubes, in: IEEE 14th International Conference on Computational Science and Engineering, CSE, 2011, pp. 488-491.; N. Dean, A. Ilic, I. Ramirez, J. Shen, K. Tian, On the power dominating sets of hypercubes, in: IEEE 14th International Conference on Computational Science and Engineering, CSE, 2011, pp. 488-491.
[9] Dorbec, P.; Henning, M.; Löwenstein, C.; Montassier, M.; Raspaud, A., Generalized power domination in regular graphs, SIAM J. Discrete Math., 27, 1559-1574, (2013) · Zbl 1290.05117
[10] Dorbec, P.; Mollard, M.; Klavžar, S.; Špacapan, S., Power domination in product graphs, SIAM J. Discrete Math., 22, 554-567, (2008) · Zbl 1171.05037
[11] Dorfling, M.; Henning, M. A., A note on power domination in grid graphs, Discrete Appl. Math., 154, 1023-1027, (2006) · Zbl 1090.05054
[12] Ekstrand, J.; Erickson, C.; Hall, H. T.; Hay, D.; Hogben, L.; Johnson, R.; Kingsley, N.; Osborne, S.; Peters, T.; Roat, J.; Ross, A.; Row, D. D.; Warnberg, N.; Young, M., Positive semidefinite zero forcing, Linear Algebra Appl., 439, 1862-1874, (2013) · Zbl 1283.05165
[13] Goddard, W.; Henning, M. A., Domination in planar graphs with small diameter, J. Graph Theory, 40, 1-25, (2002) · Zbl 0997.05072
[14] Guo, J.; Niedermeier, R.; Raible, D., Improved algorithms and complexity results for power domination in graphs, Algorithmica, 52, 177-202, (2008) · Zbl 1170.68031
[15] Haynes, T. W.; Hedetniemi, S. M.; Hedetniemi, S. T.; Henning, M. A., Domination in graphs applied to electric power networks, SIAM J. Discrete Math., 15, 519-529, (2002) · Zbl 1006.05043
[16] Haynes, T. W.; Hedetniemi, S. T.; Slater, S. J., Fundamentals of Domination in Graphs, (1998), CRC Press: CRC Press Boca Raton · Zbl 0890.05002
[17] Hellwig, A.; Volkmann, L., Some upper bounds for the domination number, J. Combin. Math. Combin. Comput., 57, 187-209, (2006) · Zbl 1113.05076
[18] L. Hogben, B. Wissman, Computations in Sage for Nordhaus-Gaddum problems for power domination, PDF Available at http://orion.math.iastate.edu/lhogben/NG_powerdomination-Sage.pdfhttps://sage.math.iastate.edu/home/pub/88/; L. Hogben, B. Wissman, Computations in Sage for Nordhaus-Gaddum problems for power domination, PDF Available at http://orion.math.iastate.edu/lhogben/NG_powerdomination-Sage.pdfhttps://sage.math.iastate.edu/home/pub/88/
[19] Jaeger, F.; Payan, C., Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un graphe simple, C. R. Acad. Sci. Paris Ser. A, 274, 728-730, (1972) · Zbl 0226.05121
[20] Meierling, D.; Volkmann, L., Upper bounds for the domination number in graphs of diameter two, Util. Math., 93, 267-277, (2014) · Zbl 1293.05270
[21] Nikoletseas, S.; Spirakis, P., Near optimal dominating sets in dense random graphs with polynomial expected time, (van Leeuwen, J., Graph Theoretic Concepts in Computer Science. Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 790, (1994), Springer Verlag: Springer Verlag Berlin), 1-10
[22] Nordhaus, E. A.; Gaddum, J., On complementary graphs, Amer. Math. Monthly, 63, 175-177, (1956) · Zbl 0070.18503
[23] Read, R. C.; Wilson, R. J., An Atlas of Graphs, (1998), Oxford University Press: Oxford University Press Oxford · Zbl 0908.05001
[24] Wang, Y.; Li, Q., Super-edge-connectivity properties of graphs with diameter \(2\) (Chinese, English summary), J. Shanghai Jiaotong Univ., 33, 646-649, (1999) · Zbl 0967.05042
[25] Wieland, B.; Godbole, A. P., On the domination number of a random graph, Electron. J. Combin., 8, 13, (2001), Research Paper 37 · Zbl 0989.05108
[26] Zhao, M.; Kang, L.; Chang, G. J., Power domination in graphs, Discrete Math., 306, 1812-1816, (2006) · Zbl 1099.05065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.