On the Structure of 3D Queen Domination
This work provides the first asymptotic bound for 3D queen domination, solving an open combinatorial problem for graph theorists.
The paper studies the domination number of the 3D queen graph, proving that interior queen placements dominate more core cells than boundary placements, leading to a Θ(n²) bound, and certifies exact values for n ≤ 6 via integer programming.
We study the domination number $γ(Q_n^3)$ of the three-dimensional $n \times n \times n$ queen graph. The main result is a stratified theorem computing, for each position type -- corner, edge, face, or interior -- the number of inner-core vertices dominated by a queen, and showing in particular that interior placements dominate strictly more core cells than boundary placements. This yields a symmetry-reduction principle via the octahedral group and complements the standard counting lower bound and layered upper bound, giving $γ(Q_n^3) = Î(n^2)$. We also certify exact values for $n \leq 6$ via integer linear programming and independent verification.