{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T19:39:30Z","timestamp":1649014770286},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"The queens graph $Q_{m \\times n}$ has the squares of the $m \\times n$ chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal of the board. A set $D$ of squares of $Q_{m \\times n}$ is a dominating set\u00a0for $Q_{m \\times n}$ if every square of $Q_{m \\times n}$ is either in $D$ or adjacent to a square in $D$. The minimum size of a dominating set of $Q_{m \\times n}$ is the domination number, denoted by $\\gamma(Q_{m \\times n})$.
\nValues of $\\gamma(Q_{m \\times n}), \\, 4 \\leq m \\leq n \\leq 18,\\,$ are given here, in each case with a file of minimum\u00a0dominating sets (often all of them, up to symmetry) in an online appendix. In these ranges for $m$ and $n$, monotonicity fails once: $\\gamma(Q_{8\\times 11}) = 6 > 5 = \\gamma(Q_{9 \\times 11}) = \\gamma(Q_{10 \\times 11}) = \\gamma(Q_{11 \\times 11})$.
\nLet $g(m)$ [respectively $g^{*}(m)$] be the largest integer such that $m$ queens suffice to dominate the $(m+1) \\times g(m)$ board [respectively, to dominate the $(m+1) \\times g^{*}(m)$ board with no two queens in a row]. Starting from the elementary bound $g(m) \\leq 3m$, domination when the board is far from square is investigated. It is shown (Theorem 2) that $g(m) = 3m$ can only occur when $m \\equiv 0, 1, 2, 3, \\mbox{or } 4 \\mbox{ (mod 9)}$, with an online appendix showing that this does occur for $m \\leq 40, m \\neq 3$. Also (Theorem 4), if $m \\equiv 5, 6, \\mbox{or } 7 \\mbox{ (mod 9)}$ then $g^{*}(m) \\leq 3m-2$, and if $m \\equiv 8 \\mbox{ (mod 9)}$ then $g^{*}(m) \\leq 3m-4$. It is shown that equality holds in these bounds for $m \\leq 40 $.
\nLower bounds on $\\gamma(Q_{m \\times n})$ are given. In particular, if $m \\leq n$ then $\\gamma(Q_{m \\times n}) \\geq \\min \\{ m,\\lceil (m+n-2)\/4 \\rceil \\}$.
\nTwo types of dominating sets (orthodox covers and centrally strong sets) are developed; each type is shown to give good upper bounds of $\\gamma(Q_{m \\times n})$ in several cases.
\nThree questions are posed: whether monotonicity of $\\gamma(Q_{m \\times n})$ holds (other than from $(m, n) = (8, 11)$ to $(9, 11)$), whether $\\gamma(Q_{m \\times n}) = (m+n-2)\/4$ occurs with $m \\leq n < 3m+2$ (other than for $(m, n) = (3, 3)$ and $(11, 11)$), and whether the lower bound given above can be improved.
\nA set of squares is independent if no two of its squares are adjacent. The minimum size of an independent dominating set of $Q_{m \\times n}$ is the independent domination number, denoted by $i(Q_{m \\times n})$. Values of $i(Q_{m \\times n}), \\, 4 \\leq m \\leq n \\leq 18, \\,$ are given here, in each case with some minimum dominating sets. In these ranges for $m$ and $n$, monotonicity fails twice: $i(Q_{8\\times 11}) = 6 > 5 = i(Q_{9 \\times 11}) = i(Q_{10 \\times 11}) = i(Q_{11 \\times 11})$, and $i(Q_{11 \\times 18}) = 9 > 8 = i(Q_{12\\times 18})$.<\/jats:p>","DOI":"10.37236\/6026","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T01:01:52Z","timestamp":1578618112000},"source":"Crossref","is-referenced-by-count":0,"title":["Domination of the Rectangular Queen's Graph"],"prefix":"10.37236","volume":"26","author":[{"given":"S\u00e1ndor","family":"Boz\u00f3ki","sequence":"first","affiliation":[]},{"given":"P\u00e9ter","family":"G\u00e1l","sequence":"additional","affiliation":[]},{"given":"Istv\u00e1n","family":"Marosi","sequence":"additional","affiliation":[]},{"given":"William D.","family":"Weakley","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2019,12,4]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i4p45\/7974","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i4p45\/HTML","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i4p45\/7974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T23:01:11Z","timestamp":1579215671000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v26i4p45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,10,11]]}},"URL":"http:\/\/dx.doi.org\/10.37236\/6026","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":["Computational Theory and Mathematics","Geometry and Topology","Theoretical Computer Science","Applied Mathematics","Discrete Mathematics and Combinatorics"],"published":{"date-parts":[[2019,12,4]]}}}