Giraffe Graph

A giraffe graph is a graph formed by all possible moves of a hypothetical chess piece called a "giraffe" which moves analogously to a knight except that it is restricted to moves that change by one square along one axis of the board and four squares along the other. To form the graph, each chessboard square is considered a vertex, and vertices connected by allowable giraffe moves are considered edges. It is therefore a -leaper graph.

Giraffe graphs are bicolorable, bipartite, class 1, perfect, triangle-free, and weakly perfect.

The square () giraffe graph is connected for .

It is traceable for , 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, and 20, with the status of 11 open.

The smallest nontrivial square board allowing a closed tour for the giraffe (i.e., the giraffe graph is Hamiltonian) is the , first solved by A. H. Frost in 1886 (Jelliss 2001). For , the square board is Hamiltonian for , 10, 12, 14, 16, 18, and 20.

Precomputed properties of giraffe graphs will be implemented in a future version of the Wolfram Language as GraphData["Giraffe", m, n].

EFERENCES

Jelliss, G. "The Big Beasts: Giraffe 1, 4." §10.33 in Knight's Tour Notes. 2019. http://www.mayhematics.com/p/KTN10_Leapers.pdf