TY - JOUR
T1 - Edge domination in grids
AU - Klostermeyer, William F.
AU - Yeo, Anders
PY - 2015
Y1 - 2015
N2 - 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).
AB - 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).
KW - Edge dominating set
KW - Total dominating set
KW - Vertex cover
UR - http://www.scopus.com/inward/record.url?scp=84962678472&partnerID=8YFLogxK
M3 - Journal article
AN - SCOPUS:84962678472
VL - 95
SP - 99
EP - 117
JO - Journal of Combinatorial Mathematics and Combinatorial Computing
JF - Journal of Combinatorial Mathematics and Combinatorial Computing
SN - 0835-3026
ER -