This is an old revision of the document!
Hypercube graph
Set
$ n\in\mathbb N, n\ge 1 $ |
$ V\equiv \{0,1\}^n $ |
$Q_n\equiv \langle V,E\rangle$ |
$ k\in\mathbb N,1\le k\le n $ |
$ v,w\in V $ |
$ \{v,w\}\in E\leftrightarrow \exists!k.\ \pi_k(v)\neq\pi_k(w) $ |
Discussion
The Hypercube graph, also called n-cube, has vertices all n-tuples of 0's and 1's and two such vertices are connected iff they differ in one coordinate.
E.g. $V(Q_2)=\{\langle 0,0\rangle,\langle 0,1\rangle,\langle 1,0\rangle,\langle 1,1\rangle\}$ and there are all but the diagonal relations are edges in the graph. Clearly $Q_n$ is just a square.
Parents
Subset of
Requirements