The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Graph-Maker-Other-19
River stage zero No dependents
1 ++
/ Graph::Maker::RookGrid

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.

2x2 and 3x2 grids are circular ladders the same as Graph::Maker::CircularLadder.

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

    1310    1,1        single vertex
    19655   1,2        path-2
    1374    1,3        3-cycle
    74      1,4        complete-4
    462     1,5        complete-5
    232     1,6        complete-6
    58      1,7        complete-7
    180     1,8        complete-8
    674     2,2        4-cycle
    746     2,3        circular ladder 3 rungs
    33461   2,4        cross-connected complete-4s
    32441   2,5        cross-connected complete-5s
    32796   2,6        cross-connected complete-6s
    6607    3,3        Paley
    32804   3,4
    30317   4,4        Paley
    1022    2,2,2      cube
    32808   2,2,3
    1340    2,2,2,2    tesseract
    28533   2,2,2,2,2  5-hypercube

OEIS

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

    A085537    NxN Wiener index
    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

    graph complement
      A292058    NxN Wiener index

SEE ALSO

Graph::Maker, Graph::Maker::Grid, Graph::Maker::Complete, Graph::Maker::Hypercube

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