Hypercube graph | |
---|---|
![]() The hypercube graph Q4 | |
Vertices | 2n |
Edges | 2n – 1n |
Diameter | n |
Girth | 4 if n ≥ 2 |
Automorphisms | n! 2n |
Chromatic number | 2 |
Spectrum | |
Properties | Symmetric Distance regular Unit distance Hamiltonian Bipartite |
Notation | Qn |
Table of graphs and parameters |
In graph theory, the hypercube graph Qn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.
The hypercube graph Qn may also be constructed by creating a vertex for each subset of an n-element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n-digit binary number, with two vertices adjacent when their binary representations differ in a single digit. It is the n-fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of Qn – 1 connected to each other by a perfect matching.
Hypercube graphs should not be confused with cubic graphs, which are graphs that have exactly three edges touching each vertex. The only hypercube graph Qn that is a cubic graph is the cubical graph Q3.