Chapter 10, Problem 30SE

A simple graph can be used to determine the minimum number of queens on a chessboard that control the entire chessboard. An $n\times n$chessboard hasn²squares in an $n\times 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 hasn²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.

30. How can the adjacency matrix of $\stackrel{\_}{G}$be found from the adjacency matrix of G, whereGis a simple graph?