A Note on Algebraic Hypercube Colorings
Irene Finocchi, Emanuele G. Fusco, Rossella Petreschi · 2008
An L(1, 1)-coloring of the n-dimensional hypercube Qnassigns nodes of Qnwhich are at distance les 2 with different colors. Such colorings find application, e.g., in frequency assignment in wireless networks and data distribution in parallel memory systems. Let chi2macr(Qn) be the minimum number of colors used in any L(1, 1)-coloring. Finding the exact value of chi2macr(Qn) 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 Qnare 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 chi2macr(Qn), independently of the choice of the group operation.