The covering radius of Hadamard codes in odd graphs

The 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=2^m’-¹, where this Hadamard code can be chosen to be a subcode of the punctured first order Reed-Muller code Rm(1,m). The authors 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. The authors find upper and lower bounds on this integer, and determine it for small values of k. The present study suggests a new isomorphism test for Hadamard designs.