/ 
Graph-Maker-Other-7
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
+------+------+------+------+

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

3x3, cyclic, https://hog.grinvin.org/ViewGraphInfo.action?id=6607 (Paley 9)
3x4, https://hog.grinvin.org/ViewGraphInfo.action?id=21067

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

LICENSE

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