- HOUSE OF GRAPHS
- SEE ALSO
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.
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 => 1 makes the grid wrap-around at its sides. For 2 dimensions this is knight moves on a torus.
For 1 dimension like
dims =>  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 =>  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
cyclicare in the style of
Graph::Maker::Grid. Other parameters are passed to the constructor, either
Graph::Maker::Grid, if the graph is directed (the default) then edges are added both forward and backward between vertices. Option
undirected => 1creates an undirected graph and for it there is a single edge between vertices.
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
- 3x3, cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=6607 (Paley 9)
- 3x4, https://hog.grinvin.org/ViewGraphInfo.action?id=21067
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
Copyright 2015, 2016, 2017 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/.