On embedding complete graphs into hypercubes

AbstractAn embedding of Kn into a hypercube is a mapping, gf, of the n vertices of Kn to distinct vertices of the hypercube. The associated cost is the sum over all pairs of vertices, vi, vj, i⩽j, of the (Hamming) distance between gf(vi) and gf(vj). Let tf(n) denote the minimum cost over all embeddings of Kn into a hypercube (of any dimension). In this note we prove that tf(n) = (n − 1)2 unless n = 4 or 8, in which case tf(n) = (n − 1)2 − 1. As an application, we use this theorem to derive an alternate proof of the fact that the Isolation Heuristic (and its accompanying variants) for the multiway cut problem of Dahlhaus et al. (1994) are tight for all n. This result also gives a combinatorial justification for the seemingly anomalous improvements that these variants achieve in the cases n = 4 and 8