Nordhaus–Gaddum conjecture for power domination

From papers

Let GG be a graph of order nn, and let G\overline{G} denote its complement. Assume that every component of both GG and G\overline{G} has order at least 33. Write γP(G)\gamma_P(G) for the power domination number of GG. Nordhaus–Gaddum conjecture for power domination.

γP(G)+γP(G)n3+2.\gamma_P(G)+\gamma_P(\overline{G})\le \left\lfloor\frac{n}{3}\right\rfloor+2.

The bound would show that the exceptional orders 13,14,16,17,2013,14,16,17,20 arising in the preceding result are not genuine exceptions. The paper notes that no counterexamples are known, while the conjecture remains unresolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Katherine F. Benson, Daniela Ferrero, Mary Flagg, Veronika Furst, Leslie Hogben and Violeta Vasilevska, “Note on Nordhaus-Gaddum problems for power domination”, arXiv:1610.03115 (2016).

Additional references

2 papers in this index state this conjecture (2016). The statement above is taken from the most recent of them; the others are arXiv:1608.01189.

Solutions 0

No solutions have been posted yet.