The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Graph-Maker-Other-19
River stage zero No dependents
1 ++
/ Graph::Maker::Circulant

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

    74      N=4 1,2     tetrahedral

    226     N=6 1,2     octohedral
    84      N=6 1,3     complete bipartite 3,3
    746     N=6 2,3     circular ladder 3 rungs

    710     N=7 1,2
    58      N=7 1,2,3

    160     N=8 1,2
    570     N=8 1,3
    176     N=8 1,2,3      sixteen cell
    36263   N=8 1,2,4
    33454   N=8 1,3,4
    180     N=8 1,2,3,4
    640     N=8 1,4        Mobius ladder 4 rungs
    116     N=8 2,4        two complete-4s

    328     N=9 1,3
    33801   N=9 1,2,3      symmetric configuration
    370     N=9 1,2,4
    328     N=9 1,2,3,4

    21063   N=10 1,2
    32519   N=10 1,3
    36276   N=10 1,5       Mobius ladder 5 rungs
    138     N=10 2,4       two complete-5
    36274   N=10 2,5
    21117   N=10 1,2,4     cross-linked complete-5s
    148     N=10 1,2,3,4
    152     N=10 1,2,3,4,5
    20611   N=10 1,2,5
    252     N=10 1,3,5
    142     N=10 1,2,3,5
    32441   N=10 2,4,5  

    21065   N=13 1,5       cyclotomic
    19514   N=13 1,2,5

    20688   N=16 1,2,5,8
    30395   N=17 1,2,4,8   a Ramsey 4,4

SEE ALSO

Graph::Maker, Graph::Maker::Cycle, Graph::Maker::Complete, Graph::Maker::RookGrid

HOME PAGE

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

LICENSE

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