TOPICS
Search

Camel Graph


CamelGraphs

A camel graph is a graph formed by all possible moves of a hypothetical chess piece called a "camel" 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 three squares along the other. To form the graph, each chessboard square is considered a vertex, and vertices connected by allowable camel moves are considered edges. It is therefore a (1,3)-leaper graph, as well as the Euclidean distance-sqrt(10) graph.

The term "camel graph" dates back to at least T. R. Dawson, who used it in his 'Caissa's Playthings' column in Cheltenham Examiner in 1913 (Jelliss 2019).

Ball and Coxeter (1987, p. 186) state, "Euler's method [to construct a Hamiltonian cycle] can be applied to find routes of this kind: for instance, he applied it to find a re-entrant route by which a piece that moved two cells forward like a castle [rook] and then one cell like a bishop would occupy in succession all the black cells on the board." Such a series of moves corresponds to a camel tour (Jelliss 2019).

Like bishop graphs, camel graph are disconnected (except for the trivial singleton graph on a 1×1 board which is trivially connected), with each component being restricted to either black or white squares. Again, as with the bishop graph, the black and white components of an m×n camel graph are isomorphic iff m and n are not both odd.

The 5×5 camel graph consists of a connected white component and a disconnected black component which, as in the case of the 3×3 knight graph, includes a central (unreachable from all of the other squares) isolated vertex.

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

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


See also

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

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987.Dawson, T. R. "Caissa's Playthings." Cheltenham Examiner. 1913.Dawson, T. R. L'Echiquier. 1928.Hansson, F. Problem 715 in Problemist Fairy Chess Supplement. April and June 1933.Jelliss, G. "The Big Beasts: Camel {1, 3}Shaped Boards." §10.27 in Knight's Tour Notes. 2019. http://www.mayhematics.com/p/KTN10_Leapers.pdfKraitchik, M. Le Problème du Cavalier. 1927.

Referenced on Wolfram|Alpha

Camel Graph

Cite this as:

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

Subject classifications