The kth border-bishop domination problem
Abstract
Considered in this paper is a special case of the bishop's domination problem, called the kth border bishop's domination problem. Given an n x n board, the domination number for the bishop's graph, when the squares are restricted to only squares along the edge of the board (called the 1st border), is denoted by Bor(Bn,1). The second border squares are defined as the set of squares that border the original border squares. In a similar fashion, one can extend the original domination problem until a dominating set becomes impossible to find. In this paper, it is shown that if domination is possible, Bor(Bn,k) = 2n - 4k + 2 when n = 2,3 (mod 4). For the cases where n = 0,1 (mod 4), if domination is possible Bor(Bn,k) = 2n - 4k + 2 unless k = [n/4] + 1. In these cases Bor(Bn,k) = 2n - 4k + 4 and Bor(Bn,k) = 2n - 4k + 3, respectively. It is also shown that for k > [n/4] + 1 no dominating set exists. The natural extension of the question is to ask how many ways are there to place the bishops along the kth border so that every square is dominated. If domination is possible, the answers are given as (n - 4k + 5)(n - 4k + 7) x 4n-3k for odd n and (n - 4k + 6)2 x 4n-3k for even n, unless k = [n/4]+ 1 and n = 0,1 (mod 4). In which case the answers are 2n/2-2 and 2n+1/2 for n > 1, respectively. Besides the mathematical proofs, a Java program is given to find all border bishop dominating sets. Also found is the size and number of minimum border-dominating sets of rooks.
