NAME

Graph::Maker::FoldedHypercube - create folded hypercube graph

SYNOPSIS

 use Graph::Maker::FoldedHypercube;
 $graph = Graph::Maker->new ('folded_hypercube', N => 4);

DESCRIPTION

Graph::Maker::FoldedHypercube creates a Graph.pm graph of a folded hypercube of order N. This is a hypercube N where each pair of antipodal vertices are merged,

    num vertices = /  1       if N=0
                   \ 2^(N-1)  if N>=1
                 = 1, 1, 2, 4, 8, 16, ...   (A011782)

The effect is an N-1 hypercube with the addition of edges between antipodal vertices within that N-1 hypercube. For example N=3 is an N-1=2 square with additional edges between opposing corners

    3---4
    | X |      N => 3   (is complete-4)
    1---2

Vertices are numbered 1..2^(N-1) as per a hypercube of order N-1. The extra edges are each v to 2^(N-1)+1 - v.

N=0 is a singleton vertex, since that's all the hypercube 0 has and nothing is merged.

N=1 is a singleton too, being a pair of vertices merged.

The graph is regular with degree N apart from initial exceptions,

    degree = / 0,0,1   if N=0,1,2 respectively
             \ N       otherwise
           = 0, 0, 1, 3, 4, 5, 6, ...

Total number of edges are then

    num edges = 1/2 * (num vertices * degree)
              = / 0,0,1            if N = 0,1,2
                \ N * 2^(N-2)      if N >= 3
              = 0, 0, 1, 6, 16, 40, 96, 224, ...  (A057711)

FUNCTIONS

$graph = Graph::Maker->new('folded_hypercube', 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 both ways between vertices. Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.

FORMULAS

Edges

It's convenient to think of hypercube vertices numbered 0 to 2^(N-1)-1 inclusive (instead of 1..2^(N-1)). Edges are

    u,v   differing at exactly one bit position
    u,v   differing at all N-1 bit positions,
            so u = 2^(N-1)-1 - v

HOUSE OF GRAPHS

House of Graphs entries for the folded hypercubes here include

https://hog.grinvin.org/ViewGraphInfo.action?id=1310 (etc)

    1310    N=0,1  single vertex
    19655   N=2    path-2
    74      N=3    complete 4
    570     N=4    complete bipartite 4,4
    975     N=5    Clebsch, cyclotomic 16, Keller 2
    1206    N=6    Kummer
    49239   N=7
    49241   N=8

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to the folded hypercube include

http://oeis.org/A011782 (etc)

    A011782   num vertices
    A057711   num edges
    A295921   total cliques

SEE ALSO

Graph::Maker, Graph::Maker::Hypercube, Graph::Maker::Keller

HOME PAGE

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

LICENSE

Copyright 2019, 2020, 2021, 2022 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/.

cpanm Graph::Maker::Other

perl -MCPAN -e shell
install Graph::Maker::Other