Evènement pour le groupe GT Graphes et Applications


Date 2011-07-01  14:00-15:00
TitreThe 2-distance coloring of the Cartesian product of cycles using optimal Lee codes. 
RésuméLet Cm be the cycle of length m. We denote the Cartesian product of n copies of Cm by G(n, m) := Cm x Cm x · · · x Cm . The k-distance chromatic number χk (G) of a graph G is χ(Gk ) where Gk is the kth power of the graph G = (V, E) in which two distinct vertices are adjacent in Gk if and only if their distance in G is at most k. The k-distance chromatic number of G(n, m) is related to optimal codes over the ring of integers modulo m with minimum Lee distance k + 1. In this paper, we consider χ2 (G(n, m)) for n = 3 and m ≥ 3. In particular, we compute exact values of χ2 (G(3, m)) for 3 ≤ m ≤ 8 and m = 4k, and upper bounds for m = 3k or m = 5k, for any positive integer k. We also show that the maximal size of a code in Z3 with minimum Lee distance 3 is 26. 
LieuSalle 178 
OrateurSeog-Jin Kim 
UrlDepartment of Mathematics Education, Konkuk University, Korea 



1 document lié: