On two $q$-ary $n$-cube coloring problems

Abstract

Let $\ddot{I}{‡}_d^{\prime }(n,q)$ (resp. $\ddot{I}{‡}_d(n,q)$) denote the minimum number of colors necessary to color a $q$-ary $n$-cube so that no two vertices that are at a distance at most $d$ (resp. exactly $d$) get the same color. These two problems were proposed in the study of scalability of optical networks. In this paper, we provide upper and lower bounds on $\ddot{I}{‡}_d^{\prime }(n,q)$ and $\ddot{I}{‡}_d(n,q)$ when $q$ is a prime power.