NAME
Graph::Maker::Petersen  create Petersen and generalized Petersen graphs
SYNOPSIS
use Graph::Maker::Petersen;
$graph = Graph::Maker>new ('Petersen');
$graph = Graph::Maker>new ('Petersen', N=>7, K=>3);
DESCRIPTION
Graph::Maker::Petersen
creates a Graph.pm
graph of the Petersen graph,
___1___
____/  \____
/  \
2__ 6 __5 N => 5
 7/\10  K => 2
 \/ \/  (the defaults)
 / \ / \ 
 __8/ \9__ 
   
34
Parameters N
and K
give generalized Petersen graphs. For example
$graph = Graph::Maker>new('Petersen', N=>7, K=>3);
N
is the number of vertices in the outer cycle, and the same again in the inner circulant. K
is how many steps between connections for the inner. In the default Petersen 5,2 for example at inner vertex 6 step by 2 for edge 68. The outer vertices are numbered 1 .. N
and the inner N+1 .. 2*N
.
Should have N >= 3
and K != 0 mod N
. K=1 is an inner vertex cycle the same as the outer.
K will usually be in the range 1 <= K <= N/2. Other values are accepted but become the same as something in that range since the K steps wraparound and go as both K and K mod N. So for example 7,9 and 7,5 are both the same as 7,2.
N=4,K=1 is equivalent to the cube graph (Graph::Maker::Hypercube of 3 dimensions). N=4,K=2 is equivalent to a Mobius ladder of 4 rungs with 2 consecutive rungs deleted.
FUNCTIONS
$graph = Graph::Maker>new('Petersen', key => value, ...)

The key/value parameters are
N => integer, number of outer vertices (and corresponding inner) K => integer, step for inner circulant graph_maker => subr(key=>value) constructor, default Graph>new
Other parameters are passed to the constructor, either
graph_maker
orGraph>new()
.If the graph is directed (the default) then edges are added both ways 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
 N=3, K=1, https://hog.grinvin.org/ViewGraphInfo.action?id=746, circular ladder 3 rungs
 N=4, K=1, https://hog.grinvin.org/ViewGraphInfo.action?id=1022 (cube)
 N=4, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=588
 N=5, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=660 (Petersen)
 N=7, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=28482
 N=8, K=3, https://hog.grinvin.org/ViewGraphInfo.action?id=1229 (Mobius Kantor)
 N=9, K=3, https://hog.grinvin.org/ViewGraphInfo.action?id=6700
 N=10, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=1043 (Dodecahedral)
 N=10, K=3, https://hog.grinvin.org/ViewGraphInfo.action?id=1036 (Desargues)
 N=11, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=24052
 N=12, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=27325
 N=12, K=5, https://hog.grinvin.org/ViewGraphInfo.action?id=1234 (Nauru)
OEIS
A few of the many entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include
http://oeis.org/A077105 (etc)
A077105 number of nonisomorphic K for given N,
K <= floor((N1)/2), so not K=N/2 when N even
A182054 number of independent sets in N,2 for even N
A182077 number of independent sets in N,2 for odd N
A274047 diameter of N,2
SEE ALSO
Graph::Maker, Graph::Maker::Cycle, Graph::Maker::Hypercube
LICENSE
Copyright 2015, 2016, 2017, 2018, 2019 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/.