TOPICS
Search

Giraffe Graph


GiraffeGraphs

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 (1,4)-leaper graph.

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

The square (n×n) giraffe graph is connected for n>=8.

It is traceable for n=1, 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 10×10, first solved by A. H. Frost in 1886 (Jelliss 2001). For n<=20, the square board is Hamiltonian for n=1, 10, 12, 14, 16, 18, and 20.

Precomputed properties of giraffe graphs are implemented in the Wolfram Language as GraphData[{"Giraffe", {m, n}}].


See also

Antelope Graph, Camel Graph, Fairy Chess, Fiveleaper Graph, Knight Graph, Leaper Graph, Zebra Graph

Explore with Wolfram|Alpha

References

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

Cite this as:

Weisstein, Eric W. "Giraffe Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GiraffeGraph.html

Subject classifications