square board, and for even , the -domination number is when and . In a similar fashion, the -tuple domination number is when is odd and less than . Hamiltonicity Every rook's graph contains a Hamiltonian cycle. However, these cycles may involve moves between squares that are far apart within a single row or column of the chessboard. Instead, the study of "rook's tours", in the mathematics of chess, has generally concentrated on a special case of these Hamiltonian cycles where the rook is restricted to move only to adjacent squares. These single-step rook's tours only exist on boards with an even number of squares. They play a central role in the proof of Gomory's theorem that, if two squares of opposite colors are removed from a standard chessboard, the remaining squares can always be covered by dominoes. They are featured alongside knight's tours in the first work to discuss chesspiece tours, the 9th century Sanskrit Kavyalankara of Rudrata. Spectrum The spectrum of a rook's graph (the eigenvalues of its adjacency matrix) consists of the four eigenvalues , , , and . Because these are all integers, rook's graphs are integral graphs. There are only three classes of graphs (and finitely many exceptional graphs) that can have four eigenvalues with one of the four being ; one of the three classes is the class of rook's graphs. For most combinations of and , the rook's graph is spectrally unique: no other graph has the same spectrum. In particular this is true when or , or when the two numbers and sum to at least 18 and do not have the form . See also King's graph, knight's graph, queen's graph, and bishop's graph, four other graphs defined from the moves of chess pieces Lattice graph, the graph of horizontal and vertical adjacencies of squares on a chessboard References External links Mathematical chess problems Perfect graphs Parametric families of graphs Regular graphs Strongly regular graphs