The Integrity of the Cube is Small

It is shown that the integrity of the n-dimensional cube is O(2n log n/ √ n). Barefoot, Entringer and Swart [1] introduced the graphical parameter integrity. Let m(H) denote the maximum number of vertices in a component of a graph H. Then the integrity of a graph G, denoted I(G), is defined by I(G) = min{ |S| + m(G− S) : S ⊂ V (G) }. In [2] the values of the integrity of some product graphs were calculated. One such graph for which the integrity was not calculated was the cube. The ndimensional cube Qn has 2 n vertices, and may be defined as the cartesian product of n copies of Q1, where Q1 is the complete graph on 2 vertices. In [2] it was conjectured that I(Qn) was 2 n−1+1. We show here that this value is considerably too high. The Upper Bound One approach to cutting up the cube is as follows. You find a suitable set Dn of integers, and then select any vertex x and for each d ∈ Dn, remove all the vertices of distance d from x. Indeed, this approach can be used to show that I(Qn) is O(2n/n1/4), and thus that the conjectured value of I(Qn) is incorrect. But the approach described below is better. Consider an n-dimensional cube Qn where n is a power of 2. For any vertex x, we define the cut Cx to be the set of vertices at distance n/2 from x. We investigate removing a series of “orthogonal” cuts. Department of Mathematical Sciences, Indiana-Purdue University at Fort Wayne, Fort Wayne IN 46805, USA Department of Mathematics, Massachusetts Institute of Technology, Cambridge MA 02139, USA Office of Naval Research, 800 North Quincy Street, Arlington VA 22217, USA 1 Choose a collection x1, x2, . . . , xr of vertices which are pairwise distance n/2 apart as follows: x1 is given by the stringO n, x2 byO n/21n/2, x3 byO n/41n/4On/41n/4 etc. Note that r is at most 1 + log n (where log is base 2). Then let Gr = Qn − (Cx1 ∪ Cx2 ∪ . . . ∪ Cxr). Lemma. If n ≥ 4 then Gr has 2r isomorphic parts, each the union of components. Thus m(Gr) ≤ 2n−r. Proof. Label a vertex v in Gr with an r-tuple (y1, . . . , yr) where yi = +1 if v is less than n/2 away from xi in Qn, and −1 otherwise. This labeling partitions Gr into 2r parts. It is easy to see that there is no edge connecting two parts. To show that these parts are isomorphic, observe that there exists an automorphism φi of Qn which maps xi to its complement xi but keeps the other xj fixed. (For example, consider n = 4: the function which maps string x to the reversal of its complement fixes x2 and x3 but maps x1 to 1111.) Thus the composition of the relevant φi is the desired isomorphism. qed Hence we have established that: If n is a power of 2 then I(Qn) ≤ min 0≤r≤1+log n {