++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# NAME

Graph::Maker::RookGrid - create Rook grid graph

# SYNOPSIS

`````` use Graph::Maker::RookGrid;
\$graph = Graph::Maker->new ('rook_grid', dims => [8,8]);``````

# DESCRIPTION

`Graph::Maker::RookGrid` creates a `Graph.pm` graph for a grid of squares with edges connecting squares as a chess rook moves.

This means at a given vertex move anywhere in the same row or column. For higher dimensions it means any change in a single coordinate.

The `dims` parameter is the same as `Graph::Maker::Grid` but the edges here include steps bigger than 1.

``````    +------+------+------+------+    dims => [3,4]
|      |      |      |      |
|  1   |   2  |   3  |   4  |    edges 1 to 2,3,4,5,9
|      |      |      |      |          2 to 1,6,10,3,4
+------+------+------+------+          ...
|      |      |      |      |          7 to 5,6,8,3,11
|  5   |   6  |   7  |   8  |          ...
|      |      |      |      |          etc
+------+------+------+------+
|      |      |      |      |
|  9   |  10  |  11  |  12  |
|      |      |      |      |
+------+------+------+------+``````

1xN grids are complete-N graphs the same as Graph::Maker::Complete.

2x2x...x2 grids are hypercubes the same as Graph::Maker::Hypercube.

There is no `cyclic` parameter since the edges are already effectively cyclic, having for example an edge 4 to 1, and 4 to anywhere else in the row, etc.

# FUNCTIONS

`\$graph = Graph::Maker->new('rook_grid', key => value, ...)`

The key/value parameters are

``````    dims     => arrayref of dimensions
graph_maker => subr(key=>value) constructor, default Graph->new``````

`dims` is 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.

# HOUSE OF GRAPHS

House of Graphs entries for graphs here include

1x1, https://hog.grinvin.org/ViewGraphInfo.action?id=1310, single vertex
1x2, https://hog.grinvin.org/ViewGraphInfo.action?id=19655, path-2
1x3, https://hog.grinvin.org/ViewGraphInfo.action?id=1374, 3-cycle
1x4, https://hog.grinvin.org/ViewGraphInfo.action?id=74, complete-4
1x5, https://hog.grinvin.org/ViewGraphInfo.action?id=462, complete-5
1x6, https://hog.grinvin.org/ViewGraphInfo.action?id=232, complete-6
1x7, https://hog.grinvin.org/ViewGraphInfo.action?id=58, complete-7
1x8, https://hog.grinvin.org/ViewGraphInfo.action?id=180, complete-8
2x2, https://hog.grinvin.org/ViewGraphInfo.action?id=674, 4-cycle
2x3, https://hog.grinvin.org/ViewGraphInfo.action?id=746, circular ladder 3 rungs
3x3, https://hog.grinvin.org/ViewGraphInfo.action?id=6607, Paley
4x4, https://hog.grinvin.org/ViewGraphInfo.action?id=30317, Paley
2x2x2, https://hog.grinvin.org/ViewGraphInfo.action?id=1022, cube
2x2x2x2, https://hog.grinvin.org/ViewGraphInfo.action?id=1340, tesseract
2x2x2x2x2, https://hog.grinvin.org/ViewGraphInfo.action?id=28533, 5-hypercube

# OEIS

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

``````    A088699    NxN number of independent sets
A287274    NxM number of dominating sets
A287065    NxN number of dominating sets
A290632    NxM number of minimal dominating sets
A289196    NxN number of connected dominating sets
A286189    NxN number of connected induced subgraphs``````