Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650260 | Discrete Mathematics | 2008 | 7 Pages |
In this paper we introduce a variant on the long studied, highly entertaining, and very difficult problem of determining the domination number of the queen's chessboard graph, that is, determining how few queens are needed to protect all of the squares of a k by k chessboard. Motivated by the problem of minimum redundance domination, we consider the problem of determining how few queens restricted to squares on the border can be used to protect the entire chessboard. We give exact values of “border-queens” required for the kk by kk chessboard when 1⩽k⩽131⩽k⩽13. For the general case, we present a lower bound of k(2-9/2k-8k2-49k+49/2k) and an upper bound of k-2k-2. For k=3t+1k=3t+1 we improve the upper bound to 2t+12t+1 if 3t+13t+1 is odd and 2t2t if 3t+13t+1 is even.We generalize this problem to (A,B)(A,B)-restricted parameters for vertex subsets A and B of V(G)V(G) where, for example, one must use only vertices in A to dominate all of B. Defining upper and lower parameters for independence, domination, and irredundance, we present a generalization of the “domination chain” of inequalities relating these parameters.