Cayley Graph Representation and Graph Product Representation of Hypercubes
Hypercube Q(n) is a well-known graph structure having three different kinds of equivalent definitions that are: I. binary n bit sequences with the adjacency condition, 2. Q(1) = K(2), Q(n) = Q(n-1) square K(2), where square means the Cartesian product, 3. the Cayley graph on Z(2)(n) with the generator set {10 ... 0, 010 ... 0, ... , 0 ... 01}. We give a necessary and sufficient condition for a set of binary sequences to be a generator set for the hypercube. Then, we give relations between some generator sets and relational products. These results show the wide variety of representability of hypercubes which would be used for many applications.
cayley graph hypercube relational product labeling