++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# NAME

Graph::Maker::Circulant - create circulant graph

# SYNOPSIS

`````` use Graph::Maker::Circulant;
\$graph = Graph::Maker->new ('circulant', N=>8, offset_list=>[1,4]);``````

# DESCRIPTION

`Graph::Maker::Circulant` creates `Graph.pm` circulant graphs. The graph has vertices 1 to N. Each vertex v has an edge to v+offset, for each offset in the given `offset_list`. v+offset is taken mod N in the range 1 to N.

Offsets will usually be 1 <= offset <= N/2. Anything bigger can be reduced mod N, and any bigger than N/2 is equivalent to some -offset, and that is equivalent to an edge v-offset to v. Offset 0 means a self-loop at each vertex.

A single `offset_list => [1]` gives a cycle the same as Graph::Maker::Cycle. Bigger single offset is a cycle with vertices in a different order, or if offset and N have a common factor then multiple cycles.

In general, if N and all offsets have a common factor g then the effect is g many copies of circulant N/g and offsets/g.

A full `offset_list` 1..N/2 is the complete graph the same as Graph::Maker::Complete.

If a factor m coprime to N is put through all `offset_list` then the resulting graph is isomorphic. Edges are m*v to m*v+m*offset which is the same by identifying m*v in the multiple with v in plain. For example circulant N=8 offsets 1,4 is isomorphic to offsets 3,4, the latter being multiple m=3. If an offset list doesn't have 1 but does have some offset coprime to N then dividing through mod N gives an isomorphic graph with 1 in the list.

Circulant N=6 2,3 is isomorphic to the rook grid 3x2 per Graph::Maker::RookGrid.

# FUNCTIONS

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

The key/value parameters are

``````    N           => integer, number of vertices
offset_list => arrayref of integers
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, excluding cycles and completes, include

N=6 1,2 https://hog.grinvin.org/ViewGraphInfo.action?id=226, octohedral
N=6 1,3 https://hog.grinvin.org/ViewGraphInfo.action?id=84, complete bipartite 3,3
N=6 2,3 https://hog.grinvin.org/ViewGraphInfo.action?id=746, circular ladder 3 rungs
N=7 1,2 https://hog.grinvin.org/ViewGraphInfo.action?id=710

N=8 1,2 https://hog.grinvin.org/ViewGraphInfo.action?id=160
N=8 1,3 https://hog.grinvin.org/ViewGraphInfo.action?id=570
N=8 1,2,3 https://hog.grinvin.org/ViewGraphInfo.action?id=176, sixteen cell
N=8 1,4 https://hog.grinvin.org/ViewGraphInfo.action?id=640, Mobius ladder 4 rungs
N=8 2,4 https://hog.grinvin.org/ViewGraphInfo.action?id=116, two complete-4s

N=9 1,3 https://hog.grinvin.org/ViewGraphInfo.action?id=328
N=9 1,2,4 https://hog.grinvin.org/ViewGraphInfo.action?id=370

N=10 1,2 https://hog.grinvin.org/ViewGraphInfo.action?id=21063
N=10 2,4 https://hog.grinvin.org/ViewGraphInfo.action?id=138, two complete-5
N=10 1,2,4 https://hog.grinvin.org/ViewGraphInfo.action?id=21117, cross-linked complete-5s
N=10 1,2,3,4 https://hog.grinvin.org/ViewGraphInfo.action?id=148
N=10 1,2,5 https://hog.grinvin.org/ViewGraphInfo.action?id=20611
N=10 1,3,5 https://hog.grinvin.org/ViewGraphInfo.action?id=252
N=10 1,2,3,5 https://hog.grinvin.org/ViewGraphInfo.action?id=142