The covering radius of Hadamard codes in odd graphs

AbstractThe use of odd graphs has been proposed as fault-tolerant interconnection networks. The following problem originated in their design: what is the graphical covering radius of an Hadamard code of length 2k − 1 and size 2k − 1 in the odd graph Ok? Of particular interest is the case of k=2m−1, where we can choose this Hadamard code to be a subcode of the punctured first order Reed-Muller code RM(1,m). We define the w-covering radius of a binary code as the largest Hamming distance from a binary word of Hamming weight w to the code. The above problem amounts to finding the k-covering radius of a (2k,4k,k−1) Hadamard code. We find upper and lower bounds on this integer, and determine it for small values of k. Our study suggests a new isomorphism test for Hadamard designs