An Independent Border-Free Type-A Cover of Q221 and Improved Asymptotic Bounds for Queen Domination

Source abstract

The queen's graph $Q_n$ has the squares of the $n\times n$ chessboard as vertices, with adjacency defined by a common row, column, or diagonal. We give an explicit set of 111 pairwise nonattacking queens on $Q_{221}$. The set contains no queen on an outer row or column and satisfies the original type-A 1-cover conditions of Ostergard and Weakley with parameters $(e,f,u)=(24,23,31)$. A direct enumeration checks all $221^2=48{,}841$ board squares and finds none uncovered. The lower bound of Finozhenok and Weakley therefore gives $γ(Q_{221})=i(Q_{221})=111$. Neuhaus previously established the equality for ordinary domination. The no-edge-square branch of the type-A amplification theorem gives $γ(Q_N)\leq(112/221)N+O(1)$ and $i(Q_N)\leq(113/221)N+O(1)$. These coefficients improve, respectively, the coefficients $30/59$ and $91/177$ stated by Neuhaus. We also describe the exact four-family matching model used to obtain the certificate. An assignment-dual identity gives a lossless reduced-cost deletion rule, and alternating allowed-edge tests give a second lossless reduction. The complete coordinates, two independently implemented standard-library certificate verifiers, and a deterministic reduction audit accompany the manuscript.