Hypercube graph

Definition

A $n$ -dimensional hypercube graph is defined in the follwing equivalent ways:

It is the graph of the $n$ -dimensional hypercube, i.e., the graph whose vertices are the vertices of the $n$ -dimensional hypercube and whose edges are the edges of the $n$ -dimensional hypercube.
It is defined inductively as follows: for $n = 1$ , it is the complete graph:K2, and for $n \geq 2$ , it is the prism of the $(n - 1)$ -dimensional hypercube.

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	$2^{n}$	Each time we increment $n$ by 1, the number of vertices doubles
size of edge set	$n \cdot 2^{n - 1}$	By the definition of prism, if $a_{n}$ denotes the number of edges in the $n$ -hypercube, then $a_{n} = 2 a_{n - 1} + 2^{n - 1}$ . Further, $a_{1} = 1$ . We solve the recurrence relation and obtain the expression.

Numerical invariants associated with vertices

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	$n$	Each time we apply the prism construction, the degree goes up by 1.
eccentricity of a vertex	$n$	Each time we apply the prism construction, the eccentricity of every vertex goes up by 1.

Other numerical invariants

Function	Value	Explanation
clique number	2	The graph is bipartite, hence triangle-free
independence number	$2^{n - 1}$	Thinking geometrically in terms of the hypercube, the graph is bipartite, with the two parts defined by the parity of the sums of coordinates of vertices if we coordinatize the hypercube as ${0, 1}^{n}$ . Both parts have sizes $2^{n - 1}$ .
chromatic number	2	Thinking geometrically in terms of the hypercube, the graph is bipartite, with the two parts defined by the parity of the sums of coordinates of vertices if we coordinatize the hypercube as ${0, 1}^{n}$ .
radius of a graph	$n$	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	$n$	Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
girth of a graph	4 (except the case $n = 1$ , that has infinite girth)	The 2-hypercube is cycle graph:C4. All higher hypercubes contain this as a subgraph.
odd girth	infinite	Thinking geometrically in terms of the hypercube, the graph is bipartite, with the two parts defined by the parity of the sums of coordinates of vertices if we coordinatize the hypercube as ${0, 1}^{n}$ .
even girth	4 (except the case $n = 1$ , that has infinite girth)	The 2-hypercube is cycle graph:C4. All higher hypercubes contain this as a subgraph.