Abstract :
It is well known that the set of all ‘even’ spanning subgraphs of a connected graph G on n vertices with m edges forms a binary linear code C=CE(G) with parameters [m,m−n+1,g], where g is the girth of G. Such codes were first studied by Bredeson and Hakimi; IEEE Trans. Inform. Theory 13 (1967) 348–349 and Hakimi and Bredeson, IEEE Trans. Inform. Theory 14 (1968) 584–591 in the late 1960s who were concerned with the problems of augmenting C to a larger [m,k,g]-code and of efficiently decoding such codes; similar results for ternary and q-ary graphical codes were given in Hakimi and Bredeson, IEEE Trans. Inform. Theory, 15 (1969) 435–436 and Bobzow and Hakimi, IEEE Trans. Inform. Theory 17 (1971) 215–218, respectively. Recently, the present authors Jungnickel and Vanstone, Bull. ICA 18 (1966) 45–64 have obtained considerable progress in the binary case by generalizing Hakimiʹs and Bredesonʹs construction method to obtain better augmenting codes and by giving a much more efficient decoding algorithm. In a further paper of Jungnickel and Vanstone, J. Combin. Math. Combin. Comput., in press, we adapted our methods to obtain similar progress in the ternary case; in this final paper, we shall transfer our results to q-ary graphical codes.
