Ternary Graphical Codes

Abstract

It is well-known that the set of all circulations of a connected digraph $G$ on $p$ vertices with $q$ edges forms a ternary linear code $\text{C}={\text{C}}_E(G)$
with parameters $[q,q–p+1,g]$, where $g$ is the girth of $G$. Such codes were first studied by Hakimi and Bredeson $[8]$ in $1969$, who investigated problems
of augmenting $\text{C}$ to a larger $(q,k,g)$-code and efficiently decoding such codes. Their treatment was similar to their previous work on binary codes $[4,7]$.
Recently, we have made significant progress in the binary case by generalizing Hakimi’s and Bredeson’s construction method to obtain better augmenting codes and developing a more efficient decoding algorithm. In this paper, we explore how our methods can be
adapted to achieve corresponding progress in the ternary case. In particular, we will correct an oversight in a graph-theoretic lemma of Bredeson and Hakimi, which affects their decoding algorithms and discuss alternative decoding procedures based on a connection to a challenging optimization problem.