Solved: A simple graph can be used to determine the

Chapter , Problem 26E

(choose chapter or problem)

A simple graph can be used to determine the minimum number of queens on a chessboard that control the entire chessboard. An n ×n chessboard has n2 squares in an n×n configuration. A queen in a given position controls all squares in the same row, the same column, and on the two diagonals containing this square, as illustrated. The appropriate simple graph has n2 vertices, one for each square, and two vertices are adjacent if a queen in the square represented by one of the vertices controls the square represented by the other vertex. Explain how the concept of a minimum dominating set applies to the problem of determining the minimum number of queens controlling an n × n chessboard.