/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::HalvedHypercube

NAME

Graph::Maker::HalvedHypercube - create halved hypercube graph

SYNOPSIS

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

DESCRIPTION

Graph::Maker::HalvedHypercube creates a Graph.pm graph of a "halved hypercube" of order N. This starts from the hypercube N and is halved by replacing the edge set with pairs of vertices which had been distance-2 apart. This results in two isomorphic connected components, which are each the halved hypercube N.

The effect is an N-1 hypercube to which edges are added between vertices distance 2 apart (and existing edges retained).

Vertices are numbered 1..2^(N-1) as per a hypercube of order N-1.

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

Edges are each u to v where in binary u-1 and v-1 differ at exactly 1 or 2 bit positions. So degree regular and

degree = binomial(N-1,1) + binomial(N-1,2)
       = N*(N-1)/2

num_edges = num_vertices * degree / 2
          = 2^(N-3) * N*(N-1)
          = 0, 0, 1, 6, 24, 80, 240, 672, ...   (A001788)

N=0 is a singleton vertex, and so is N=1.

N=2 is a square with diagonal cross edges (vertices distance 2 apart), so a complete-4.

N=4 is the "sixteen-cell" graph, and also 8-circulant with offsets 1,2,3 (Graph::Maker::Circulant).

N=5 is the complement of the Clebsch graph.

FUNCTIONS

$graph = Graph::Maker->new('halved_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.

HOUSE OF GRAPHS

House of Graphs entries for the halved hypercubes here include

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

1310    N=0,1  singleton
19655   N=2    path-2
74      N=3    complete 4
176     N=4    sixteen cell
49258   N=5    Clebsch comlement
49260   N=6
49262   N=7
49264   N=8

OEIS

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

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

A011782   num vertices
A161680   vertex degree
A001788   num edges
A005864   independence number
A288943   number of independent sets

SEE ALSO

Graph::Maker, Graph::Maker::Hypercube, Graph::Maker::FoldedHypercube

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