Bishop's graph

Each vertex represents a square on the chessboard and each edge represents a legal move of the bishop; that is, there is an edge between two vertices (squares) if they occupy a common diagonal.

The fact that the chessboard has squares of two colors, say red and black, such that squares that are horizontally or vertically adjacent have opposite colors, implies that the bishop's graph has two connected components, whose vertex sets are the red and the black squares, respectively.

A component of the bishop's graph can be treated as a rook's graph on a diamond if the original board is square and has sides of odd length, because if the red squares (say) are turned 45 degrees, the bishop's moves become horizontal and vertical, just like those of the rook.

The minimum number of bishops needed to dominate a square board of side n is exactly n, and this is also the smallest number of bishops that can form an independent dominating set.

By contrast, a total domination set, which is a dominating set for which every square, including those occupied by bishops, is attacked by one of the bishops, requires more bishops; on the square board of side n ≥ 3, the least size of a total dominating set is