The k-Distance Independence Number and 2-Distance Chromatic Number of Cartesian Products of Cycles.

A set S⊆V(G)<inline-graphic></inline-graphic> is a k-distance independent set of a graph G if the distance between every two vertices of S is greater than k. The k-distance independence number αk(G)<inline-graphic></inline-graphic> of G is the maximum cardinality over all k-distance independent sets in G. A k-distance coloring of G is a function f from V(G) onto a set of positive integers (colors) such that for any two distinct vertices u and v at distance less than or equal to k we have f(u)≠f(v)<inline-graphic></inline-graphic>. The k-distance chromatic number of a graph G is the smallest number of colors needed to have a k-distance coloring of G. The k-distance independence numbers and 2-distance chromatic numbers of Cartesian products of cycles are considered. A computer-aided method with the isomorphic rejection is used to determine the k-distance independence numbers of Cartesian products of cycles. By using these results, several lower and upper bounds on the maximal cardinality AqL(n,d)<inline-graphic></inline-graphic> of a q-ary Lee code of length n with a minimum distance at least d are improved. It is also established that the 2-distance chromatic number of G equals |V(G)|α(G2)<inline-graphic></inline-graphic> for G=Cm□Cn□Ck<inline-graphic></inline-graphic>, whenever k≥3<inline-graphic></inline-graphic> and (m,n)∈{(3,3),(3,4),(3,5),(4,4)}<inline-graphic></inline-graphic> or k, m and n are all multiples of seven. Moreover, it is shown that the 2-distance chromatic number of the three-dimensional square lattice is equal to seven. [ABSTRACT FROM AUTHOR]