Name
Abstract | ||
|---|---|---|
In this paper, we study the following two hypercube coloring problems: given n and d, find the minimum number of colors, denoted as @g"d^'(n) (resp. @g"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 @g"5^'(2^r^+^1)=4^r^+^1 for any odd number r=3, and give two upper bounds on @g"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 @g"d(n) and @g"d^'(n). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.dam.2013.07.006 | Discrete Applied Mathematics |
Keywords | Field | DocType |
optical network,hamming distance,new result,z4-linear,small n,- hypercube,different color,minimum number,linear codes,odd number,coloring problem,coding theory,upper bound,hypercube | Discrete mathematics,Combinatorics,Vertex (geometry),Upper and lower bounds,Coding theory,Hamming distance,Mathematics,Hypercube | Journal |
Volume | Issue | ISSN |
161 | 18 | 0166-218X |
Citations | PageRank | References |
3 | 0.49 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fu Fang-Wei | 1 | 381 | 57.23 |
| San Ling | 2 | 1284 | 108.96 |
| Chaoping Xing | 3 | 916 | 110.47 |