Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Graphs Associated with Codes of Covering Radius 1 and Minimum Distance 2. | Graphs Associated with Codes of Covering Radius 1 and Minimum Distance 2 Joanne L. Hall School of Mathematical and Geospatial Sciences Royal Melbourne Institute of Technology Department of Mathematics Australian National University Submitted Dec 10 2007 Accepted Apr 23 2008 Published May 5 2008 Mathematics Subject Classifications 94B65 05C15 05B15 The search for codes of covering radius 1 led Ostergảrd Quistorff and Wasser-mann to the OQW method of associating a unique graph to each code 9 . We present results on the structure and existence of OQW-associated graphs. These are used to find an upper bound on the size of a ball of radius 1 around a code of length 3 and minimum distance 2. OQW-associated graphs and non-extendable partial Latin squares are used to catalogue codes of length 3 over 4 symbols with covering radius 1 and minimum distance 2. 1 Introduction The search for the minimum or maximum cardinality of an object with a set of properties is one of the classical problems in combinatorics. An n V d qR code C is a code of length n over q symbols with V codewords a minimum Hamming distance of d and covering radius of R. n V d q or n V qR are used if the covering radius or minimum distance are not specified. Let Kq n R be the minimum V such that an n V qR code exists and Aq n d be the maximum V such that an n V d q code exists. The problems of finding Kq n R and Aq n d are well studied. The Delsarte bound 4 and the Hamming bound 7 are some well know early results. For more recent studies see 2 8 . The study of codes with both specified covering radius and minimum distance is more recent and has mostly been studied using covering radius 1 and minimum distance 2 10 9 1 5 . n V 2 q 1 codes are also of interest as they are equivalent to non-extendable partial Latin hypercubes 5 . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R68 1 a Figure 1 A graph which has no OQW-associated code. This article provides a summary and extension of the .
