𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Coloring Problem in Hamming Spaces

✍ Scribed by Patric R.J. Östergård

Book ID
102566451
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
219 KB
Volume
18
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

The R -domatic number of a graph is the maximum number of colors that can be used to color the vertices of the graph so that all vertices of the graph have at least one vertex of each color within distance R . In this paper the problem of determining the R -domatic number of the n -cube , P ( n , R ) , is considered . The value P (6 , 1) ϭ 5 is settled , and a conjecture by Laborde that P ( n , 1) ϳ n as n tends to infinity is proved . Best known upper and lower bounds on the R -domatic number of the n -cube are given for n р 16 and R р 7 .

📜 SIMILAR VOLUMES

A coloring problem
A coloring problem
✍ V. L. Dol'nikov 📂 Article 📅 1973 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 725 KB
On Identifying Codes in Binary Hamming S
On Identifying Codes in Binary Hamming Spaces
✍ Iiro Honkala; Antoine Lobstein 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 138 KB

A binary code C f0; 1g n is called r-identifying, if the sets B r ðxÞ \ C; where B r ðxÞ is the set of all vectors within the Hamming distance r from x; are all nonempty and no two are the same. Denote by M r ðnÞ the minimum possible cardinality of a binary r-identifying code in f0; 1g n : We prove