++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
+------+------+------+------+``````

## 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 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`. (It 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

3x3, cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=6607 (Paley 9)
3x4, https://hog.grinvin.org/ViewGraphInfo.action?id=21067

# 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``````