# Algebraic properties of graph of chess pieces

For the purpose of this question, a chess piece is the King, Queen, Rook, Bishop or Knight of the game of chess. To a chess piece is attached a graph which represents the legal moves it can make on an empty chess board. Except for the bishop, the graph attached to a chess piece has 64 vertices, while the bishop's graph has 32 vertices.

These graphs satisfy a number of interesting mathematical properties from the point of view of graph theory.

• Only the rook's graph is regular, and the rook's graph is even strongly regular (a fact well-known to chess player with no knowledge of mathematics).
• The knight's graph is bipartite.
• The king's, rook's, queen's and bishop's graph are hamiltonian (and after Euler, it is very well-known though to me non-obvious a priori that the knight's graphs is hamiltonian).

Less obvious properties have of course been devised by graph theorists.

Recently, I asked myself (with no other purpose than leisure) if these graphs were known to satisfy interesting algebraic properties.

A quick computation based on its strong regularity or on the observation that it is the cartesian product of two copies of the complete graph $$K_8$$ show that spectrum of the rook's graph is $$\{14^{(1)},6^{(14)},-2^{(49)}\}$$ (in particular, it is an integral graph).

Are there any other remarkable algebraic properties of the graphs of chess pieces, either of their spectra or of their group of automorphisms?

• My guess is that you will get nicer properties for a toroidal chessboard. Dec 18 '19 at 0:38
• Or a Klein bottle! At the risk of getting slightly off-topic, I can't resist mentioning some chess puzzles on a Klein bottle that I once composed. Dec 18 '19 at 16:43

• Great answer! The OP is encouraged to see in particular the Friedman-Hanlon Theorem [Thm 3.2 in Wachs's survey]. It relates the reduced cohomology of $m \times n$ chessboard complexes to irreducible representations of products of symmetric groups $S_m \times S_n$. Dec 17 '19 at 23:59
The rook's graph is $$K_8 \Box K_8$$, i.e., the Cartesian product of $$K_8$$ and $$K_8$$.
The chromatic polynomial $$P(K_8 \Box K_8;n)$$ of the rook's graph is the number of $$8 \times 8$$ generalized Latin squares, where we can use $$n$$ symbols (without repeated symbols in any row or column). In particular, evaluating it at its chromatic number...
$$P(K_8 \Box K_8;8) = \text{number of Latin squares of order 8}.$$