Two results about the hypercube

Next, we consider the integrity I(Qn) of the hypercube, defined as I(Qn)=min{|S|+m(Qn∖S):S⊆V(Qn)},where m(H) denotes the number of vertices in the largest connected component of H. Beineke, Goddard, Hamburger, Kleitman, Lipman and Pippert showed that c2nn≤I(Qn)≤C2nnlogn and suspected that their upper bound is the right value. We prove that the truth lies below the upper bound by showing that I(Qn)≤C2nnlogn.