Kings graph

Kings graph --- королевский граф.

The kings graph [math]\displaystyle{ K_{n} }[/math] is a graph whose vertex set consists of the squares of [math]\displaystyle{ n \times n }[/math] chessboard, where two vertices are adjacent if and only if a king can move from one square to the other in a single move according to the chess rules. More formally, [math]\displaystyle{ V(K_{n}) = \{(i,j): \; 1 \leq i,j \leq n\} }[/math], where distinct [math]\displaystyle{ (i,j) }[/math] and [math]\displaystyle{ (i',j') }[/math] are adjacent if and only if [math]\displaystyle{ |i - i'|, |j - j'| \leq 1 }[/math]