Edge domination in grids

William F. Klostermeyer, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review


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 languageEnglish
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Pages (from-to)99-117
Publication statusPublished - 2015
Externally publishedYes


  • Edge dominating set
  • Total dominating set
  • Vertex cover


Dive into the research topics of 'Edge domination in grids'. Together they form a unique fingerprint.

Cite this