Cube Graphs
Table of Contents

Cube Graphs

Definition: A Cube Graph is a graph that is obtained by taking all vertices denoted as binary words and joining the vertices with the edge whenever the binary words differ by $1$.

Cube graphs are denoted by $Q_k$ where $k$ refers to the length of the binary works. For example if $k = 1$ we will have vertices labelled "$0$" and "$1$". If $k = 2$ will have vertices labelled "$00$, "$01$, "$10$", and "$11$". Let's look at the graphs of $Q_1$, $Q_2$, and $Q_3$:


As you can see, each vertex that is connected to another by an edge differs by only either $0$ or $1$.

Also, the degree of each vertex is $k$ since edges are formed only by one difference in binary words where the different occurs in both $k$ placeholders forming the edge.

The number of vertices of cube graphs is $2^k$ and the number of edges of a cube graph is $k \cdot 2^{k-1}$ according to The Handshaking Lemma.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License