Parametric families of graphs | Regular graphs
Hypercube graph
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 Q3 that is a cubic graph is the cubical graph Q3. (Wikipedia).
