Edge domination in grids

William F. Klostermeyer, Anders Yeo

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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).

TidsskriftJournal of Combinatorial Mathematics and Combinatorial Computing
Sider (fra-til)99-117
StatusUdgivet - 2015
Udgivet eksterntJa


Dyk ned i forskningsemnerne om 'Edge domination in grids'. Sammen danner de et unikt fingeraftryk.