Edge Domination in Grids

Abstract

It has been conjectured that the edge domination number of the $m\times n$ grid graph, denoted by ${\gamma }^{\prime }(P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)$, is $\lceil mn/3\rceil$ when $m,n\ge 2$. Our main result gives support for this conjecture by proving that $\lceil mn/3\rceil \le {\gamma }^{\prime }(P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)\le mn/3+n/12+1$, when $m,n\ge 2$. We furthermore show that the conjecture holds when $mn$ is a multiple of three and also when $m\le 13$. Despite this support for the conjecture, our proofs lead us to believe that the conjecture may be false when $m$ and $n$ are large enough and $mn$ is not a multiple of three. We state a new conjecture for the values of ${\gamma }^{\prime }(P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)$.