  The guessing number of a directed graph (digraph), equivalent to the entropy
of that digraph, was introduced as a direct criterion on the solvability of a
network coding instance. This paper makes two contributions on the guessing
number. First, we introduce an undirected graph on all possible configurations
of the digraph, referred to as the guessing graph, which encapsulates the
essence of dependence amongst configurations. We prove that the guessing number
of a digraph is equal to the logarithm of the independence number of its
guessing graph. Therefore, network coding solvability is no more a problem on
the operations made by each node, but is simplified into a problem on the
messages that can transit through the network. By studying the guessing graph
of a given digraph, and how to combine digraphs or alphabets, we are thus able
to derive bounds on the guessing number of digraphs. Second, we construct
specific digraphs with high guessing numbers, yielding network coding instances
where a large amount of information can transit. We first propose a
construction of digraphs with finite parameters based on cyclic codes, with
guessing number equal to the degree of the generator polynomial. We then
construct an infinite class of digraphs with arbitrary girth for which the
ratio between the linear guessing number and the number of vertices tends to
one, despite these digraphs being arbitrarily sparse. These constructions yield
solvable network coding instances with a relatively small number of
intermediate nodes for which the node operations are known and linear, although
these instances are sparse and the sources are arbitrarily far from their
corresponding sinks.
