/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::KnightGrid

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

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

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