/ 
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

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

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