Nordhaus–Gaddum conjecture for power domination

About 10 years old · traced to

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.

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.