++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# 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__   |
| --             -- |
3-------------------4``````

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 vertices. In the default Petersen 5,2 for example at inner vertex 6 step by 2 for edge 6--8. 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. N=4,K=1 is the cube graph, the same as Graph::Maker::Hypercube of 3 dimensions.

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 wrap-around. For example 7,9 is the same as 7,2, and 7,5 the same as 7,2 too, since steps are effectively forward and backward by K.

# 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` or `Graph->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
N=4, K=1, https://hog.grinvin.org/ViewGraphInfo.action?id=1022 (cube)
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=4, https://hog.grinvin.org/ViewGraphInfo.action?id=1229 (Moebius 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)

# OEIS

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

``````    A077105   number of non-isomorphic K for given N,
K <= floor((N-1)/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``````