++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors


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


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


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 => 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.)


$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.


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


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


Graph::Maker, Graph::Maker::Grid


Copyright 2015, 2016, 2017, 2018, 2019 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.