1-Perfect Codes Over the Quad-Cube

A vertex subset <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> of a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> constitutes a 1-perfect code if the one-balls centered at the nodes in <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula> effect a vertex partition of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. This paper considers the quad-cube <inline-formula> <tex-math notation="LaTeX">$CQ_{m}$ </tex-math></inline-formula> that is a connected <inline-formula> <tex-math notation="LaTeX">$(m+2)$ </tex-math></inline-formula>-regular spanning subgraph of the hypercube <inline-formula> <tex-math notation="LaTeX">$Q_{4m+2}$ </tex-math></inline-formula>, and shows that <inline-formula> <tex-math notation="LaTeX">$CQ_{m}$ </tex-math></inline-formula> admits a vertex partition into 1-perfect codes iff <inline-formula> <tex-math notation="LaTeX">$m=2^{k}-3$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$k\ge 2$ </tex-math></inline-formula>. The scheme for that purpose makes use of a procedure by Jha and Slutzki that constructs Hamming codes using a Latin square. The result closely parallels the existence of a 1-perfect code over the dual-cube, which is another derivative of the hypercube.


I. INTRODUCTION
A 1-PERFECT code has the capability to correct a single error, and detect two or fewer errors. Applications abound in areas such as communication systems, network systems, multiprocessor systems, and computer architecture in the wide digital world. Not surprisingly, the topic commands a rich literature [10]. Among various codes, the 1-perfect Hamming codes and 3-perfect Golay codes based on the topology of the hypercube, are the foremost [10], [15].
A quad-cube (formally defined below) is a special version of a more general network topology called the metacube, devised by Li et al. [19], that itself is derivable from the hypercube. The basic idea is to mitigate the problem of the rapid increase in the degree of the hypercube when the node size exceeds several million. It retains most good characteristics of the hypercube, notably, efficient collective communication, high connectivity, fault tolerance, low diameter, and easy routing [19]. This paper adds another significant property to that list, viz., a vertex partition of the graph into 1-perfect codes.
In an analogous study, the author [14] earlier presented a perfect code over the dual-cube that is another (relatively simpler) version of the metacube.
Motivation: Assuming that there is a maximum of one error, any possible word in a message transmission can, in a unique way, be corrected to one of the words in a 1-perfect code. Optimal resource placement in an interconnection network is another area of application. In particular, elements of a 1-perfect code may be viewed as nodes that Manuscript  house (expensive) resources such as power sources, function libraries and algorithmic information, whereas other nodes are users of the resources. Since every user node is adjacent to a unique resource node, optimality is achieved in the number of resource nodes. A closely related concept is that of domination. Indeed, a 1-perfect code corresponds to a smallest (independent) dominating set in the graph in an obvious way. Other applications include construction of an efficient backbone for routing and partition of a network into small clusters.

A. Related Studies
Apart from the study of perfect codes on hypercube-like networks, there have been a number of such studies in other settings, too. For example, Biggs [2] presented codes on the topology of general graphs, and Kratochvil [17], [18] later followed with several useful results. The stimulus comes from applications of the idea in engineering, computer science and the related disciplines.
Products of graphs [6] are natural candidates where to seek perfect codes. Not surprisingly, they command a rich literature. In particular, the famous r-perfect Lee metric codes by Golomb and Welch [7] are over the Cartesian product of finitely many cycles. For later studies in this area, see Špacapan [22] and Mollard [21]. For r-perfect codes over the Kronecker product (also known as direct product and tensor product) of finitely many cycles, the author [11]- [13] presented several results that eventually led to a complete characterization by Žerovnik [25]. For analogous studies over the strong product and the lexicographic product, see Abay-Asmerom et al. [1] and Taylor [23], respectively.

B. Definitions and Preliminaries
A graph connotes a finite, simple, undirected and connected graph. Let G be a graph, and let dist(u, v) denote the (shortest) distance between vertices u and v in G [24]. Further, let dia(G) denote the diameter of G, i.e., the largest of the distances between any two nodes in G.
For a vertex subset S of a graph G, let S denote its closed neighborhood, i.e., S ∪ {x ∈ V (G) | x is adjacent to some vertex in S}. S is said to constitute a dominating set of G if S = V (G). If, in addition, the distance between any two distinct elements of S is at least three, then S constitutes a 1-perfect code. Thus the closed neighborhoods of the vertices This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ in a 1-perfect code are mutually exclusive and collectively exhaustive.
The problem of obtaining a smallest dominating set is NP-complete, and so is the problem of deciding whether or not a graph admits a 1-perfect code [18]. For any undefined term, see West [24].
For n-bit binary strings x and y, let Ham(x, y) denote the Hamming distance between the two, i.e., the number of bit positions in which they differ from each other. The n-dimensional hypercube Q n (also called the n-cube) is the graph on the vertex set {0, 1} n , where nodes x and y are adjacent iff Ham(x, y) = 1.
Let x · y (or xy) denote the concatenation of the binary strings x and y, and for sets X and Y of binary strings, let X • Y := {xy | x ∈ X and y ∈ Y }. Meanwhile let a := 1 − a, where a ∈ {0, 1}. Definition 1.1: For an n-bit binary string x = b n−1 . . . b 0 (so 0 ≤ x ≤ 2 n − 1 in decimal), let x (a) be the n-bit integer obtainable from x by replacing b a by b a , where 0 ≤ a ≤ n−1.
It is clear that x (0) , . . . , x (n−1) are precisely the neighbors of x in Q n . See Table I for an illustration, where n = 3, and x, x (0) , x (1) , and x (2) are in decimal. Definition 1.2: For n-bit binary strings x and y, let x y denote the n-bit string obtainable by the bitwise XOR operation between x and y. Further, for integers r and s, where 0 ≤ r, s ≤ 2 n − 1, let r s denote the integer N (b(r) b(s)), where b(r) and b(s) are n-bit strings that represent r and s, respectively.
Note: A precise definition of N (x) appears below, x being a binary string. Proposition 1.1 (Gale [5]): 1) is commutative as well as associative.
Remark: The XOR operation between two bits is viewable as an addition modulo two. Proposition 1.2: Let x and y be n-bit binary strings, and let 0 ≤ a, b ≤ n − 1. Then Proposition 1.3: Let X and Y be sets of n-bit strings of equal cardinality. Then 1) X (a) = Y iff Y (a) = X, and 2) If X (a) = Y , then there exists a "perfect" matching between X and Y , given by x ↔ x (a) . Definition 1.4: For m ≥ 1, the quad-cube CQ m is a spanning subgraph of the hypercube Q 4m+2 . Its edge set is given by The nodes of CQ m are distinguishable into four types, as follows: • Type 0: those that are of the form u00 (binary) or 4i + 0 (decimal) • Type 1: those that are of the form u01 (binary) or 4i + 1 (decimal) • Type 2: those that are of the form u10 (binary) or 4i + 2 (decimal), and • Type 3: those that are of the form u11 (binary) or 4i + 3 (decimal). Let e ∈ E(CQ m ). Call e an edge of Type i if e ∈ E i , 0 ≤ i ≤ 3, and call e a cross edge if e ∈ E 4 . See Figure 1 for a depiction of the five edge types. Meanwhile, a node of the hypercube/quad-cube is viewable both as a binary string, say, x and as the corresponding nonnegative integer N (x). A formula for the latter appears below.
Proof: CQ m is a regular graph of degree m + 2, so the closed neighborhood of each vertex in it consists of m+3 vertices. In that light, the existence of a 1-perfect code requires that m + 3 divide |V (CQ m )| = 2 2m+1 , i.e., m + 3 must be a power of two. Hence the result.
The central objective of this paper is to prove that the converse of Corollary 1.5 holds true. For the special case of CQ 1 , see Figure 2, where nodes that are circled constitute a 1-perfect code of the graph. It is further clear from the depiction that this graph admits a vertex partition into such codes.  Proposition 1.6 ( [19]): CQ m admits a vertex partition into a total of 2 3m+2 m-cubes, segregated into four kinds as follows.
• Collection 0 (based on the nodes of Type 0) in which the i-th cube is on the vertex set • Collection 1 (based on the nodes of Type 1) in which the i-th cube is on the vertex set {2 2m+2 q + 4r • Collection 2 (based on the nodes of Type 2) in which the i-th cube is on the vertex set {2 3m+2 q + 4r , and r = i mod 2 2m . • Collection 3 (based on the nodes of Type 3) in which the i-th cube is on the vertex set {4i Figure 3 for a set of certain 5-cubes in CQ 5 . Definition 1.6: For an integer i and a set S of integers, let

C. A Special Latin Square
An r × r Latin square is a matrix, in which each of 0, . . . , r − 1 appears exactly once in each row and each column. Let r be a power of two. For a permutation 0 1 . . . r − 1 p 0 p 1 . . . p r−1 , let L(p 0 , . . . , p r−1 ) be the Latin square, defined below.
See Table II for M 4 and M 8 .

D. A Permutation Function π
Definition 1.8: Let r be a power of two, r ≥ 4, and let Here is how the π 2r -array is obtainable from the π r -array: • Copy the elements in the leftmost r/2 cells of the π r -array to the leftmost cells (indexed 0 to (r/2) − 1) of the π 2r -array • Copy the elements in the rightmost r/2 cells of the π r -array to the rightmost cells (indexed 3r/2 to 2r − 1) of the π 2r -array, and • Add r to each element of the π r -array, and systematically copy the resulting elements to the cells in the "middle" segment (indexed r/2 to (3r/2) − 1) of the π 2r -array. Let P r = L(π r ). See Figure 4 for the recursive structure of P 2r vis-à-vis P r . Further, π 4 , π 8 and π 16 appear in Equation (1), shown at the bottom of the page, whereas P 4 and P 8 appear in Table III.
Lemma 1.8: The i-th element and the (r − 1 − i)-th element of the π r -array differ in exactly the rightmost bit, i.e., (π r (i) Proof: Use induction on r. For r = 4, the claim follows by an inspection of π 4 . For the induction step, recall the construction of the π 2r -array from the π r -array that follows Definition 1.8, and make use of the fact that (r + π r (i)) (0) = r + (π r (i)) (0) , since r = 2 k , k ≥ 2.
Observe next that the way P r is obtainable from π r is identical to the way M r is obtainable from the identity permutation, hence the following result.
For the second identity, use induction on r to show that P r [i, r−2] = (π r (i)) (1) . To that end, first check to see that the following hold with respect to P 4 (that appears in Table III (1) . Consider P r , whose structure appears in Figure 4(a), and notice that each of L and L is an (r/2)× (r/2) matrix, where r is a power of two. The following properties are immediate: Examine P 2r next, whose structure appears in Figure 4(b). (1) (1) . Accordingly, P 2r [i, 2r − 2] = j (1) . (1) . It follows that P 2r [i, 2r−2] = r+x (1) = (r+x) (1) .
The rest of the argument is similar to that in (2) above.
. The rest of the argument is similar to that in (1) above.

E. A Distinguishing Function φ
Let k ≥ 3 and m = 2 k − 3. Definition 1.9: Let p 0 = 0, and let p 1 , . . . , p m−k be the integers between 1 and m that are not powers of two.
The statement of Definition 1.9 itself is well-defined in view of the fact that there are exactly k integers between 1 and m that are powers of two, viz., 2 0 , . . . , 2 k−1 . Here are p 0 , p 1 , . . . , p m−k for k = 4: where p 1 , . . . , p m−k are as in Definition 1.9.

F. Method of Attack
The evolution of the 1-perfect code in this paper crucially relies upon a number of concepts and results. To that end, let n = 2 k − 1, k ≥ 3, and m = n − 2.
At heart of the code construction is a scheme [15] that constructs Hamming codes using a Latin square. See Section II for the scheme itself. In a nutshell, it returns a partition of V (Q n ) into Hamming codes, say, V 0 , . . . , V n , each of cardinality 2 n−k .
Other major concepts/results employed are as follows: . Section III presents the theoretical foundation of the overall procedure. It systematically builds upon the scheme of Section II, and derives a number of results that are crucial to the correctness of the claims in the sequel.
The code construction itself relies on a vertex partition of CQ m into 2 3m subsets, each of cardinality 2 m+2 , where exactly 2 m−k+2 elements of each such subset are carefully designated as code elements, which themselves come from a set among V 0 , . . . , V m+2 . Figure 5 depicts this idea.
The foregoing vertex partition is further refined in Section IV that also presents the scheme itself. (See Figure 10.) The four sections that come next are then devoted to proving that the set returned by the main scheme is indeed a 1-perfect code of the graph.
Section IX takes the final step of proving that CQ m admits a vertex partition into 1-perfect codes, whereas Section X presents certain concluding remarks.

II. A SCHEME TO CONSTRUCT HAMMING CODES
This section recapitulates a scheme [15] that builds Hamming codes over Q n . See Algorithm 1.
Theorem 2.1: [15] For n = 2 k − 1, k ≥ 2, Algorithm 1 returns a partition, say, V 0 , . . . , V n of V (Q n ) having the following properties: 1) |V i | = 2 n /(n + 1), 0 ≤ i ≤ n, and 2) Every pair of two distinct elements in each set is at a Hamming distance of at least three, and the set is maximal with respect to this property. 9: where b i,j = 0 if u i,j is of even parity, 10: and b i,j = 1 if u i,j is of odd parity 11: end for 12: Comment: The sets C 0 , . . . , C n , and D 0 , . . . , D n together constitute a partition of V (Q n+1 ). 13: let T = (t i,j ) be the (n + 1) × (n + 1) Latin square on the identity permutation, vide Definition 1.7 14: return the sequence of sets Whereas any (n + 1) × (n + 1) Latin square (at Step 13 of Algorithm 1) would lead to a partition of V (Q n ) into Hamming codes, the schemes in this paper exclusively employ the Latin square on the identity permutation, viz., M r . (See Definition 1.7 and Table II in Section I-C.) Further, the resulting vertex partition V 0 , . . . , V n of Q n is referred to as the canonical partition, where V i = {v i,0 , . . . , v i,r−1 }, r = 2 n /(n + 1) and 0 ≤ i ≤ n. Additionally, each V i is deemed to be sorted into the ascending order. See Tables V, VI and VII that illustrate the working of the algorithm. Remark: Algorithm 1 is extendable to a scheme that leads to an upper bound on the (independent) domination number of the hypercube that is within twice the optimal [15].

III. THEORETICAL FOUNDATION This section derives a number of useful properties relating to the canonical partition
Lemma 3.1: There exists a "perfect matching" between each pair of distinct V i and V j .
Because of the distance-three property of each V j and the degree of v being equal to n, it is easy to see that v has a unique neighbor in

1) It is clear that there exists a matching between sets
It is clear that u i,k and u j,k differ in exactly the a-th bit position, so they are of different parities. Therefore, b i, j , where C i , D i , and U j are as in Algorithm 1, and where 0 ≤ i, j ≤ n. Proof: Each binary string in C i (resp. D i ) is of length n+1, whereas that in U j is of length n. The claim then follows from the fact that a is between 0 and n − 1.
Proof: Note that n The following is a key result.
Proof: Use induction on n, and make use of the notations as in Algorithm 1. For n = 3, see Figure 6 where 0 ≤ i ≤ n and 0 ≤ a ≤ n − 1, whereas the induction step calls for proving that V There are four cases.
Step 14 of Algorithm 1. Note here that each of i and a + 1 is between 0 and n = 2 k − 1, so each is a k-bit number, hence so must be i (a + 1). It follows that i (a + 1) is between 0 and n.
Note that i (a + 1) in this case is of the form 1u (binary), where u is a k-bit number. Therefore, i (a+1) is between n + 1 and 2n + 1 (decimal).
by a reasoning as in (2) Notice at this point that i and a + 1, in this case, are representable in binary as 1u and 1v, respectively, where u and v are k-bit numbers that denote (i − (n + 1)) and (a − n), respectively. In that light, i (a + 1) = (1u) (1v) = u v that is equal to (i−(n+1)) (a−n).
in this case, is between 0 and n. Figure 7 illustrates the four cases in the proof of Theorem 3.7 for the collection V 0 , . . . , V 7 with respect to Q 7 . (See Table VII in Section II for descriptions . It is clear that each of (i (a + 1)) and (i (b + 1)) is between 0 and n. Also, 4a+3 ) of four consecutive nodes in each V i contains one element each of Type 0, Type 1, Type 2, and Type 3 (not necessarily in that order), where 0 ≤ i ≤ n.
Proof: Use induction on n. For n = 7, the claim follows by an inspection of the sets in Table VII in Section II. Using the notations as in Algorithm 1, each element of V i is of the form u · v (binary), where u ∈ C p (or u ∈ D p ) and v ∈ U q for some p and q, with |u| = n + 1 and By induction hypothesis, every block of four nodes (starting at an index divisible by four) in U q has the stated property. That property is, in turn, inherited by the set C p • U q (or D p • U q ) and the union of such disjoint sets.
The next result shows that the elements in each V i are uniformly "spread out." Theorem 3.10: Recall that each element of each V i is between 0 and 2 n − 1. Therefore, the sets W i , X i , Y i and Z i are welldefined. (See Figure 8 for an illustration.) To prove the claim, use induction on n, the basis being clear from the sets that appear in Table VII in Section II. For the induction step, first examine the sets C i and D i in the "for" loop at Steps 6 − 11 in Algorithm 1, where 0 ≤ i ≤ n. The elements in each such set are between 0 and 2 n+1 − 1.
By induction hypothesis, each of U 0 , . . . , U n (appearing at Step 5 of the algorithm) has the stated property. Note next that 1) If x ∈ U i , then either 2x ∈ C i and 2x + 1 ∈ D i , or 2x + 1 ∈ C i and 2x ∈ D i , and 2) For It follows that each C i or D i admits a partition into four (sub)sets in which the elements range (i) from 0 to 2 n−1 − 1, (ii) from 2 n−1 to 2·2 n−1 −1, (iii) from 2·2 n−1 to 3·2 n−1 −1, and (iv) from 3 · 2 n−1 to 4 · 2 n−1 − 1, respectively. Consider next the sets C a • U b and D a • U b that appear in the unions at Step 14 of Algorithm 1, where 0 ≤ a, b ≤ n, and note that ) if x is in the first quarter (resp. second quarter, third quarter or fourth quarter) of C a or D a , and y ∈ U b , then 2 n x + y is in the respective quarter of It follows that each of C a •U b and D a •U b admits a partition into four subsets having the stated property. Finally, this property is seamlessly inherited by each union appearing at Step 14 of Algorithm 1.
See Figure 9 for an illustration of Definition 3.1.

IV. THE MAIN SCHEME
This section presents the main scheme that returns a 1-perfect code of CQ m . See Algorithm 2. The scheme itself relies on successive vertex partitions of the graph, depicted in Figure 10 that, in turn, is viewable as a refinement of the partition that appeared in Figure 5 in Section I. As stated earlier, the smallest unit in the vertex partition is a set of the form 2 m+2 x + {0, . . . , 2 m+2 − 1}, of which a subset 2 m+2 x + V i is designated as a set of code elements, The next four sections are devoted to proving that the set returned by the main scheme is indeed a 1-perfect code of the graph.
consists of the following sets that are mutually disjoint: . Then x = uv01 (binary) where u = 2 m c+d (decimal); |u| = m+k; |v| = m; and v01 ∈ B π(c δ(d)) . The structure of x is similar to that of the node that appears in Figure 11, with the trailing "00" replaced by "01". Note that x ≡ 1 (mod 4). Here are the m + 2 neighbors of uv01 in CQ m : • uv11 and uv00 (binary), and Notice next that d is an m-bit integer, hence so must be each of d (0) , . . . , d (m−1) . In that light, (2 m+2 Finally, it is easy to see that the sets involved are mutually disjoint. Figure 13 illustrates the argument in the proof of Lemma 5.5 for the case where m = 5. Meanwhile, the following result is analogous to Corollary 5.4. Corollary 5. 6: c2 δ(d2)) are mutually disjoint. Proof: First note that each element of 2 m+2 d + (B x ∪ D y ∪ A z ) is smaller than 2 2m+2 , and so is each element In that light, if c 1 = c 2 , then 2 m+2 (2 m c 1 + d 1 ) + B π(c1 δ(d1)) and 2 m+2 (2 m c 2 + d 2 ) + B π(c2 δ(d2)) are mutually disjoint, vide Lemma 5.5.
Let c 1 = c 2 and d 1 = d 2 next.

Lemma 5.9:
consists of the following sets that are mutually disjoint: ) . Then x = uv10 (binary), where u = 2 m c + d (decimal), |v| = m and v10 ∈ C π(c δ(d)) . The structure of x is similar to that of the node that appears in Figure 11, with the trailing "00" replaced by "10". Note that x ≡ 2 (mod 4). Here are the m + 2 neighbors of uv10 in CQ m , vide Definition 1.4: • uv00 and uv11 (binary) , the count being k, and Since c is a k-bit integer, so must be each of c (0) , . . . , c (k−1) . The rest of the argument is similar to that in the proof of Lemma 5.5. Figure 15 illustrates the argument in the proof of Lemma 5.9 for the case where m = 5.
Corollary 5.10: c2 δ(d2)) are mutually disjoint.  Proof: . This and the fact that each element of C x , D y or A z is smaller than 2 m+2 together imply that 2 m+2 (2 m p + d 1 ) + X and
Proof: Similar to that of Corollary 5.8. Remark: The expression c (t−1) may be replaced by c 2 t−1 , vide Prop. 1.2(1). Figure 16 illustrates the argument in the proof of Corollary 5.11 for the case where m = 5, where '?' indicates that the respective sets are yet to be dominated. Lemma 5.12: consists of the following sets that are mutually disjoint: (c δ(d)) . Then x = uv11 (binary), where u = 2 m c + d (decimal), |v| = m and v11 ∈ D π(c δ(d)) . The structure of x is similar to that of the node that appears in Figure 11, with the trailing "00" • uv10 and uv01 (binary), and The rest of the argument is similar to that in the proof of Lemma 5.9. Figure 17 illustrates the argument in the proof of Lemma 5.12 for m = 5, whereas Figure 18 depicts the statements of Lemmas 5.1(1)/5.5(1)/5.9(1)/5.12(1) for m = 5. Based on the distance-three property, c1 δ(d1)) and 2 m+2 (2 m c 2 + d 2 ) + D π(c2 δ(d2)) are mutually disjoint.
Proof: Similar to that of Corollary 5.10. Theorem 5.14: Algorithm 3 returns the set that dominates the following sets that are mutually disjoint: 1) The set of all elements of Type 0 between 0 and 2 2m+k+2 − 1, the count being 2 2m+k . 2) The set of all elements of Type 1 between 0 and 2 2m+k+2 − 1, the count being 2 2m+k .
Example: Let m = 5, and consider the set VI. STEP 2 The objective of the present section is to slowly "spread the wings" beyond what appeared in Section V. See Algorithm 4 that subsumes Algorithm 3. In particular, it returns a code set that is a subset of that dominates the following sets that are mutually disjoint: 1) The set of all elements of Type 0 between 2 2m+k+2 b and 2 2m+k+2 (b + 1) − 1, the count being 2 2m+k . 2) The set of all elements of Type 1 between 2 2m+k+2 b and 2 2m+k+2 (b + 1) − 1, the count being 2 2m+k .
The following is analogous to Corollary 5.15. Corollary 6.2: Among the elements between 2 2m+k+2 b and 2 2m+k+2 (b + 1) − 1, those in the following sets are not dominated by the set returned by Algorithm 4: , the number of elements being equal to (m − k)2 2m , and and p 1 , . . . , p m−k are as in Definition 1.9.

VII. STEP 3
This section focuses on the inner three loops of the main scheme, viz., Algorithm 2 of Section IV. In the process, it builds a code set that is a subset of See Figure 21 for the basic element used in Algorithm 5.
consists of the following sets that are mutually disjoint: . Proof: Similar to that of Lemma 5.1.
Proof: Make use of an argument as in the proof of Corollary 7.2, and invoke Corollary 5.6.
Lemma 7.5: consists of the following sets that are mutually disjoint: Proof: Similar to that of Lemma 5.9. The following result is analogous to Corollary 5.8.
Proof: First note the following: , then the claim follows from Corollary 5.10.
In what follows, let 1 ≤ Ham(b 1 , b 2 ) ≤ 2, and assume that 2 2m+k+2 b 1 + 2 m+2 (2 m c 1 + d 1 ) + C π(φ(b1) c1 δ(d1)) and 2 2m+k+2 b 2 + 2 m+2 (2 m c 2 + d 2 ) + C π(φ(b2) c2 δ(d2)) are not disjoint. Using notations as in the statement of Lemma 7.5 and the fact that b 1 = b 2 , it is easy to see that c 2 , d 2 ). Accordingly, there are two essential possibilities: b1) c1 δ(d1)) . The conditions on various parameters are such that the following hold: , which leads to p s+1 = 0, a contradiction, vide Definition 1.9. (Notice that Ham(b 1 , b 2 . Again, the conditions on various parameters are such that the following hold: For this equality to hold, p s+1 = 2 t . However, p s+1 is not a power of two, vide Definition 1.9; a contradiction. (Notice that Ham(b 1 , b 2 ) = 2 in this case.) consists of the following sets that are mutually disjoint: Proof: Similar to that of Lemma 5.12. Corollary 7.9: , then the claim follows from Corollary 5.13. On the other hand, if b 1 = b 2 , then the claim follows from the fact that 2 2m+k+2 is greater than the maximum of 2 m+2 (2 m c + d) + 2 m+2 − 1; and 2 m+2 is greater than each element of D Theorem 7.10: Algorithm 5 returns the set that dominates the following sets that are mutually disjoint: 1) The set of all elements of Type 0, between 0 and 2 3m+2 − 1, the count being 2 3m . 2) The set of all elements of Type 1, between 0 and 2 3m+2 − 1, the count being 2 3m .
3) The set returned by Algorithm 5 is a superset of that returned by Algorithm 4. Next, of the m + 3 sets, viz., m+2)) , the following are exactly those not dominated by the set returned by Algorithm 4, vide Corollary 6.2(1): In that light, it suffices to show that the foregoing sets are dominated by the set returned by Algorithm 5. To that end, use Corollary 7.6 and the fact that φ(b (t−1) ) = φ(b) p t (vide Lemma 1.13), whence The disjointness of the sets in this case follows from Corollary 7.7. 4) a) Immediate from Lemmas 7.8(1), 7.3(1) and 7.5(1). b) Immediate from Lemmas 7.8 (2). The disjointness of various sets in this case follows from Corollary 7.9. Figure 22 presents the count of the elements of Type 3, dominated by the set returned by Algorithm 5. Meanwhile the following is analogous to Corollary 5.15 and Corollary 6.2.

VIII. STEP 4
This section zeroes in on the main result. See Algorithm 6 that is a miniature of Algorithm 2 in Section IV. Further, see Figure 23 for the element used in this section. As usual, k ≥ 3 and m = 2 k − 3.
Proof: Similar to that of Corollary 7.2.
Proof: Similar to that of Corollary 7.4. a) φ(b) c δ(d)) consists of the following sets that are mutually disjoint: Proof: Similar to that of Lemma 7.5.
2) The (independent) domination number of CQ m is equal to the theoretical minimum of 2 4m−k+2 .

IX. VERTEX PARTITION OF THE QUAD-CUBE INTO 1-PERFECT CODES
It turns out that the main scheme admits a generalization. See Algorithm 7, where a new parameter t has been introduced, 0 ≤ t ≤ 2 k − 1.
By symmetry, every claim relating to the set returned by Algorithm 6 holds true with respect to the set returned by Algorithm 7. Hence the result.
Proof: See Figure 2 in Section I for a vertex partition of CQ 1 (m = 3 and k = 2) into 1-perfect codes. In what follows, let k ≥ 3.

X. CONCLUDING REMARKS
A quad-cube CQ m is a special case of a more general topology, called the metacube [19] that itself is derivable from the hypercube. This paper presents a vertex partition of CQ m into 1-perfect codes, where m = 2 k − 3, k ≥ 2. In an earlier study [14], the author presented an analogous result over the dual-cube that is a simpler version of the metacube.
There exist other more complex versions of the metacube, notably, the oct-cube that merit a similar study.

ACKNOWLEDGMENT
The author sincerely thanks the anonymous referees and Associate Editor Xiande Zhang for their helpful comments on the earlier draft that led to an improvement in the presentation of the article.