Article ID Journal Published Year Pages File Type
1709145 Applied Mathematics Letters 2008 4 Pages PDF
Abstract

A saw-toothed chessboard, or STC for short, is a kind of chessboard whose boundary forms two staircases from left down to right without any hole inside it. A rook at square (i,j)(i,j) can dominate the squares in row ii and in column jj. The rook problem of an STC is to determine the minimum number of rooks that can dominate all squares of the STC. In this paper, we model an STC by two particular graphs: a rook graph and a board graph. We show that for an STC, the rook graph is the line graph of the board graph, and the board graph is a bipartite permutation graph. Thus, the rook problem on STCs can be solved by any algorithm for solving the edge domination problem on bipartite permutation graphs.

Related Topics
Physical Sciences and Engineering Engineering Computational Mechanics
Authors
, ,