The King grid exponential domination lower-bound conjecture

About 8 years old · traced to

Let Kn=Pn⊠Pn\mathcal{K}_n=P_n\boxtimes P_n be the King grid, where PnP_n is the path on nn vertices. Write γe∗(G)\gamma^*_e(G) for the minimum cardinality of an exponential dominating set in a graph GG. The King grid exponential domination conjecture. For all nn,

⌈n223⌉≤γe∗(Kn).\left\lceil \frac{n^2}{23} \right\rceil \le \gamma^*_e(\mathcal{K}_n).

The conjecture would match the construction establishing asymptotic density at most 1/231/23 and the resulting upper bound for sufficiently large King grids. No matching lower bound or resolution is given in the supplied source.

References

Primary source

Michael Dairyko and Michael Young, “A linear programming method for exponential domination”, arXiv:1801.06404 (2018).

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.