++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# NAME

Graph::Maker::KnightGrid - create Knight grid graph

# SYNOPSIS

use Graph::Maker::KnightGrid;
\$graph = Graph::Maker->new ('knight_grid', dims => [8,8]);

# DESCRIPTION

Graph::Maker::KnightGrid creates a Graph.pm graph for a grid of squares with edges connecting squares as a chess knight moves.

The dims and cyclic parameters are the same as Graph::Maker::Grid but the edges here are steps 2,1.

+------+------+------+------+    dims => [3,4]
|      |      |      |      |
|  1   |   2  |   3  |   4  |    edges 1 to 7
|      |      |      |      |          1 to 10
+------+------+------+------+          2 to 9
|      |      |      |      |          2 to 11
|  5   |   6  |   7  |   8  |          2 to 8
|      |      |      |      |          ...
+------+------+------+------+          6 to 4
|      |      |      |      |          6 to 12
|  9   |  10  |  11  |  12  |          ...
|      |      |      |      |          etc
+------+------+------+------+

For 3 or more dimensions the moves are step by 2 in some coordinate and 1 in another different coordinate.

## Cyclic

cyclic => 1 makes the grid wrap-around at its sides. For 2 dimensions this is knight moves on a torus.

For 1 dimension like dims => [6] there are no edges. A knight move 2,1 means move 2 in one dimension and 1 in another. When there is only 1 dimension there is no second dimension for the second step. 2 dimensions like dims => [6,1] can be given and in that case the effect with cyclic is steps +/-1 and +/-2 along the row of vertices cycling at the ends.

For a 1x1 cyclic grid dims => [1,1], or any higher 1x1x1 etc, there is a self-loop edge since the knight move wraps around from the single vertex to itself. This is the same as the 1-vertex cyclic case in Graph::Maker::Grid. (That class also has a self-loop for 1-dimension dims => [1] whereas here that is no edges as described above.)

# FUNCTIONS

\$graph = Graph::Maker->new('knight_grid', key => value, ...)

The key/value parameters are

dims     => arrayref of dimensions
cyclic   => boolean
graph_maker => subr(key=>value) constructor, default Graph->new

dims and cyclic are in the style of Graph::Maker::Grid. Other parameters are passed to the constructor, either graph_maker or Graph->new().

Like Graph::Maker::Grid, if the graph is directed (the default) then edges are added both forward and backward between vertices. Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.

# FORMULAS

## Vertex Degree

For a 2-dimensional grid each vertex is degree up to 8 if the grid is big enough (each dimension >= 5). In a cyclic grid all vertices are this degree. For higher dimensions the degree increases. In general for D dimensions

max_degree = 4*D*(D-1)  = 0, 8, 24, 48, 80, ...       (A033996)

# HOUSE OF GRAPHS

House of Graphs entries for graphs here include

2x2, https://hog.grinvin.org/ViewGraphInfo.action?id=52, 4 disconnected
2x2 cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=674, 4-cycle
3x2, https://hog.grinvin.org/ViewGraphInfo.action?id=896
3x2 cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=226
3x3, https://hog.grinvin.org/ViewGraphInfo.action?id=126
3x3 cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=6607, Paley 9
4x2, https://hog.grinvin.org/ViewGraphInfo.action?id=684
4x2 cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=1022
4x3, https://hog.grinvin.org/ViewGraphInfo.action?id=21067
4x4 cyclic or 2x2x2x2 cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=1340, tesseract
5x2 cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=21063
2x2x2, https://hog.grinvin.org/ViewGraphInfo.action?id=68, 8 disconnected
2x2x2 cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=1022, cube
4x2x2, https://hog.grinvin.org/ViewGraphInfo.action?id=1082, four 4-cycles

# OEIS

A few of the entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include

A033996    max vertex degree in a D dimensional grid
A035008    number of edges in NxN grid
A180413    number of edges in NxNxN grid
A006075    domination number of NxN
A006076,A103315  count of ways domination number attained