Codes Based on Complete Graphs

We consider the problem of embedding the even graphical code based on the complete graph onn vertices into a shortening of a Hamming code of length 2^m-1, wherem = h(n) should be as small as possible. As it turns out, this problem is equivalent to the existence problem for optimal codes with minimum distance 5, and optimal embeddings can always be realized as graphical codes based onK _n. As a consequence, we are able to determineh(n) exactly for alln of the form 2 ^k + 1 and to narrow down the possibilities in general to two or three conceivable values.Dedicated to Hanfried Lenz on the occasion of his 80th birthdayThe research for this note was done while the first author was visiting the University of Waterloo and the University of Rome, respectively. He thanks his colleagues there for their hospitality and also acknowledges the financial support of the Consiglio Nazionale delle Ricerche (Italy). The third author acknowledges the support of the National Science and Engineering Research Council of Canada given under grant #0GP0009258.