Chang–Roussel's upper-bound conjecture for power domination in uniform hypergraphs

About 6 years old · traced to

Let H\mathcal{H} be a connected rr-uniform hypergraph on nn vertices, and let γpk(H)\gamma_p^k(\mathcal{H}) denote its kk-power domination number. Assume k+r≤nk+r\leq n. Chang–Roussel's conjecture. One has

γpk(H)≤nr+k,\gamma_p^k(\mathcal{H}) \leq \frac{n}{r+k},

with equality if and only if H\mathcal{H} is a squid hypergraph of a connected rr-uniform hypergraph, or r=2r=2 and H=Kk+2,k+2\mathcal{H}=K_{k+2,k+2}. The bound is known for r≤4r\leq 4, but the equality characterization, and indeed the conjecture itself, fails for r≥7r\geq 7, as the paper gives counterexamples.

References

Primary source

Joseph S. Alameda, Franklin Kenter, Karen Meagher and Michael Young, “An upper bound for the k-power domination number in r-uniform hypergraphs”, arXiv:2004.07918 (2022).

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.