  We consider linear network error correction (LNEC) coding when errors may
occur on edges of a communication network of which the topology is known. In
this paper, we first revisit and explore the framework of LNEC coding, and then
unify two well-known LNEC coding approaches. Furthermore, by developing a
graph-theoretic approach to the framework of LNEC coding, we obtain a
significantly enhanced characterization of the error correction capability of
LNEC codes in terms of the minimum distances at the sink nodes. In LNEC coding,
the minimum required field size for the existence of LNEC codes, in particular
LNEC maximum distance separable (MDS) codes which are a type of most important
optimal codes, is an open problem not only of theoretical interest but also of
practical importance, because it is closely related to the implementation of
the coding scheme in terms of computational complexity and storage requirement.
By applying the graph-theoretic approach, we obtain an improved upper bound on
the minimum required field size. The improvement over the existing results is
in general significant. The improved upper bound, which is graph-theoretic,
depends only on the network topology and requirement of the error correction
capability but not on a specific code construction. However, this bound is not
given in an explicit form. We thus develop an efficient algorithm that can
compute the bound in linear time. In developing the upper bound and the
efficient algorithm for computing this bound, various graph-theoretic concepts
are introduced. These concepts appear to be of fundamental interest in graph
theory and they may have further applications in graph theory and beyond.
