The King grid exponential domination lower-bound conjecture

Let Kn=PnPn\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.

Sources & referencesView supporting material

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.