/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::Crown

NAME

Graph::Maker::Crown - create crown graphs

SYNOPSIS

use Graph::Maker::Crown;
$graph = Graph::Maker->new ('crown', N => 5);

DESCRIPTION

Graph::Maker::Crown creates Graph.pm crown graphs. A crown graph is a complete bipartite N,N but without "horizontal" edges across.

Vertices are numbered 1 to 2*N inclusive. Edges are i to N+j for pairs 1<=i,j<=N and i!=j. This is like Graph::Maker::CompleteBipartite for N1=N2=N but here straight across edges i to N+i are omitted.

For N>=2, the crown is is the graph complement of the rook graph Nx2 (Graph::Maker::RookGrid). That graph is a complete set of edges within the two N columns, and edges across horizontally. The crown graph is the opposite (nothing within the columns, everything except horizontal between).

Crown N=4 is the cube graph (Graph::Maker::Hypercube 3). Crown N=5 is circulant N=10 offsets 1,3 (Graph::Maker::Circulant).

FUNCTIONS

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

The key/value parameters are

N => integer
graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either graph_maker or Graph->new().

If the graph is directed (the default) then edges are added in both directions. 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 the graphs here include

https://hog.grinvin.org/ViewGraphInfo.action?id=6901 etc

6901      N=0,  empty
19653     N=1,  two singletons
538       N=2   two path-2
670       N=3,  6-cycle
1022      N=4,  cube
32519     N=5,  circulant N=10 1,3
32794     N=6

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include

http://oeis.org/A287063 (etc)

A287063    number of dominating sets
A289121    number of minimal dominating sets
A294140    number of total dominating sets

SEE ALSO

Graph::Maker, Graph::Maker::CompleteBipartite

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

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