Abstract
It has been conjectured that the edge domination number of the m × n grid graph, denoted by γ′(Pm□Pn), is ⌊mn/3⌋, when m,n ≥ 2. Our main result gives support for this conjecture by proving that ⌊mn/3⌋ ≤ -γ′{Pm□Pn) ≤ mn/3 + n/12 + 1, when m,n ≥ 2. We furthermore show that the conjecture holds when ran is a multiple of three and also when m ≤ 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 ran is not a multiple of three. We state a new conjecture for the values of γ′(Pm□Pn).
Original language | English |
---|---|
Journal | Journal of Combinatorial Mathematics and Combinatorial Computing |
Volume | 95 |
Pages (from-to) | 99-117 |
ISSN | 0835-3026 |
Publication status | Published - 2015 |
Externally published | Yes |
Keywords
- Edge dominating set
- Total dominating set
- Vertex cover