A Note on Algebraic Hypercube Colorings

An L(1, 1)-coloring of the n-dimensional hypercube Qn assigns nodes of Qn which are at distance ≤ 2 with different colors. Such colorings find application, e.g., in frequency assignment in wireless networks and data distribution in parallel memory systems. Let Χ 2̄(Qn) be the minimum number of colors used in any L(1, 1)-coloring. Finding the exact value of Χ2̄(Q n) is still an. open problem, and only 2-approximate solutions are currently known. In this paper we expose some connections between group theory and the L(1, 1)-coloring problem. Namely, we unfold the algebraic structure on which the best available L(1, 1)-coloring algorithms of Qn are based, thus giving a group theoretic flavour to existing L(1, 1)-colorings. We show that identifying groups such that the inverse of each element is the element itself yields a simple and efficient way to obtain L(1, 1)-colorings of the hypercube. We also prove that such colorings are balanced and that every coloring algorithm based on this algebraic structure cannot improve the current upper bound on Χ2̄(Qn), independently of the choice of the group operation. © 2008 IEEE.