On covering and coloring problems for rook domains

✍ Scribed by Walter Alexandre Carnielli

• Publisher: Elsevier Science
• Year: 1985
• Tongue: English
• Weight: 456 KB
• Volume: 57
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(85)90152-9

✦ Synopsis

Given the set V~ of all vectors with length n and components 0, 1 ..... k -1 from the ring of the integers modulo k, the Hamming distance H(X, Y) between X, Y ~ V~ is defined as the number of components in which X and Y differ, and the j-dimensional rook domain of X ~ V~ is defined as the set of vectors in V~ within distance j from X.

A subset H of V~ is a (n, k, s)-covering set if V'~ can be obtained as the union of the (n-s)-dimensional rook domains of the vectors in H. The covering problem for V~ consists of the determination of the minimal cardinality T(n, k, s) of such a subset.

The search for the maximal number of disjoint (n, k, s)-covering sets is known as the coloring problem for V~ and this number is denoted by 8(n, k, s).

In this paper we obtain some general bounds for the functions T(n, k, s) and 8(n, k, s), and calculate some of their values for the cases s ~< n-2.