HypercubeGraph

The $n$-dimensional hypercube graph — $2^n$ vertices (bit strings), edges between strings differing in one bit.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageHypercubeGraph✓↗

HypercubeGraph(n)vertex $i$ (1-based) labels the bit pattern $i - 1$; edges join patterns at Hamming distance 1.

SageMathenumeratio_graph(graphs.CubeGraph(n))

Typed signatures

Type	Package	Applies
(integer) -> value	combinatorics	always

Domain: Collections

Examples

Basic #

$Q_3$: 8 vertices, $3 \cdot 2^2 = 12$ edges

live ↗

In$\bigl\lbrack\mathrm{VertexCount}(\mathrm{HypercubeGraph}(3)), \mathrm{EdgeCount}(\mathrm{HypercubeGraph}(3))\bigr\rbrack$Out$\bigl\lbrack8, 12\bigr\rbrack$

Scope #

The cube graph: $8$ vertices, joined when their binary labels differ in one bit

live ↗

In$\mathrm{HypercubeGraph}(3)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5, 6, 7, 8\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(3, 7), \mathrm{UndirectedEdge}(4, 8), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(5, 7), \mathrm{UndirectedEdge}(6, 8), \mathrm{UndirectedEdge}(7, 8)\bigr\rbrack)$

Applications #

Every vertex is at distance $3$ from its antipode, so all eccentricities are equal

live ↗

In$\mathrm{Map}(\operatorname{\_1}↦\mathrm{VertexEccentricity}(\mathrm{HypercubeGraph}(3), \operatorname{\_1}), \mathrm{VertexList}(\mathrm{HypercubeGraph}(3)))$Out$\bigl\lbrack3, 3, 3, 3, 3, 3, 3, 3\bigr\rbrack$

Properties #

Split by parity of the bit count

live ↗

In$\mathrm{IsBipartiteGraph}(\mathrm{HypercubeGraph}(3))$Out$\mathrm{True}$

The $2$-cube is the $4$-cycle

live ↗

In$\mathrm{HypercubeGraph}(2)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(2, 4), \mathrm{UndirectedEdge}(3, 4)\bigr\rbrack)$

live ↗

In$\mathrm{Sort}(\mathrm{Eigenvalues}(\mathrm{AdjacencyMatrix}(\mathrm{HypercubeGraph}(4))))$Out$\bigl\lbrack-4, -2, -2, -2, -2, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 4\bigr\rbrack$

About

Examples	6
Checked against	Wolfram Language 6 agreeSageMath 2 agree2 differ
Crosswalk	Wolfram LanguageSageMath

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: GridGraph, CompleteGraph