A graph Qn is a member of the Hypercube Graph family if it contains 2n vertices, each one with degree n, thus containing 2nn edges. A Qn graph can be generated from successive cartesian products of a K2 graph: Qn = ∏n K2.
Hypercubes of size 2n, also known as n-cubes, have an interesting property such that when representing their vertices as tuples with n binary elements, two vertices are adjacent if and only if they differ in exactly one bit. For example, in a Q4, vertex 0 (0000) is adjecent to vertices 1 (0001), 2 (0010), 4 (0100) and 8 (1000). Figure 1 shows four examples of hypercube graphs.
Figure 1: Q1,Q2,Q3, and Q4, respectively
Other properties, such as symmetry, low diameter and recursive decomposition also contribute for the study of n-cubes [7]. This family of graphs has been used on distributed computing, interconnection networks and routing.
Although n-cubes follow a pattern, being generated by K2 ×Qn−1, the problem of finding the minimum dominating set is still an open issue. The complexity increases exponentially, in function of n. In general, γ(Qn) = 2n − k when n=2k or n=2k−1[8]. It is also known that γ(Q5)=7, γ(Q6)=12, γ(Q7)=16 and γ(Qn)=2n−3 for all n ≥ 7[9].
Figure 2 depicts a minimum dominating set, in red, for a Q4, where γ(Q4)=24−2=4.
Figure 2: Dominating set 6,7,8,9 on Q4
4.1 Perfect Dominating Sets
A slightly different problem is finding a perfect dominating set (PDS) P, which only covers a graph if every vertex not in P is adjacent to exactly one vertex in P. Some properties were found regarding PDS on n-cubes and presented on [10].
Given a PDS P ⊆ Qn where n ≤ 8:
For n ≤ 2, P is a (n−1)-cube.
For 3 ≤ n ≤ 6, P is either a (n−1)-cube or P is a pair of opposite (n−3)-cubes.
For n = 7, P is either a 6-cube or P is a pair of opposite 4-cubes.
For n = 8, P is either a 7-cube or P is a pair of opposite 5-cubes or a set of sixteen edges.
