New Results on Two Hypercube Coloring Problems

Details New Results on Two Hypercube Coloring Problems New Results on Two Hypercube Coloring Problems

2010-01-13

arxiv.org/abs/1001.2209v1

Mathematics

Combinatorics

The material in this paper was presented at The Fifth Shanghai Conference on Combinatorics, May 14-18, 2005, Shanghai, China.

Scientific paper

In this paper, we study the following two hypercube coloring problems: Given $n$ and $d$, find the minimum number of colors, denoted as ${\chi}'_{d}(n)$ (resp. ${\chi}_{d}(n)$), needed to color the vertices of the $n$-cube such that any two vertices with Hamming distance at most $d$ (resp. exactly $d$) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that ${\chi}'_{4}(2^{r+1}-1)=2^{2r+1}$, ${\chi}'_{5}(2^{r+1})=4^{r+1}$ for any odd number $r\geq3$, and give two upper bounds on ${\chi}_{d}(n)$. The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small $n$. Furthermore, we derive an inequality on ${\chi}_{d}(n)$ and ${\chi}'_{d}(n)$.

Affiliated with

Also associated with

No associations

Rating

New Results on Two Hypercube Coloring Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New Results on Two Hypercube Coloring Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Results on Two Hypercube Coloring Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-525717