Menu
It has been conjectured that the edge domination number of the \( m \times n \) grid graph, denoted by \( \gamma'(P_m \Box P_n) \), is \( \lceil mn/3 \rceil \) when \( m, n \geq 2 \). Our main result gives support for this conjecture by proving that \( \lceil mn/3 \rceil \leq \gamma'(P_m \Box P_n) \leq mn/3 + n/12 + 1 \), when \( m, n \geq 2 \). We furthermore show that the conjecture holds when \( mn \) is a multiple of three and also when \( m \leq 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'(P_m \Box P_n) \).