/ 
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

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

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