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

https://hog.grinvin.org/ViewGraphInfo.action?id=52 (etc)

    52      2x2               4 disconnected
    674     2x2 cyclic        4-cycle
    896     3x2
    226     3x2 cyclic
    126     3x3
    6607    3x3 cyclic        Paley 9
    684     4x2
    1022    4x2 cyclic
    21067   4x3
    32802   4x3 cyclic        circulant N=12 1,2,5
    1340    4x4 cyclic or 2x2x2x2 cyclic,   tesseract
    21063   5x2 cyclic
    32806   6x2 cyclic        circulant N=12 1,5
    68      2x2x2             8 singletons
    1022    2x2x2 cyclic      cube
    32810   3x2x2 cyclic 
    1082    4x2x2             four 4-cycles

OEIS

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

http://oeis.org/A035008 (etc)

    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

SEE ALSO

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

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2015, 2016, 2017, 2018, 2019, 2020, 2021 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/.

cpanm Graph::Maker::Other

perl -MCPAN -e shell
install Graph::Maker::Other