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 wraparound 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 selfloop edge since the knight move wraps around from the single vertex to itself. This is the same as the 1vertex cyclic case in Graph::Maker::Grid
. (That class also has a selfloop for 1dimension 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
andcyclic
are in the style ofGraph::Maker::Grid
. Other parameters are passed to the constructor, eithergraph_maker
orGraph>new()
.Like
Graph::Maker::Grid
, if the graph is directed (the default) then edges are added both forward and backward between vertices. Optionundirected => 1
creates an undirected graph and for it there is a single edge between vertices.
FORMULAS
Vertex Degree
For a 2dimensional 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*(D1) = 0, 8, 24, 48, 80, ... (A033996)
HOUSE OF GRAPHS
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, 4cycle
 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 4cycles
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
LICENSE
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/.