Hydras: Directed hypergraphs and Horn formulas

Various bounds are given for the hydra number. We show that the hydra number of a graph can be upper bounded by the number of edges plus the path cover number of the line graph of a spanning subgraph, which is a sharp bound in several cases. On the other hand, we construct single-headed graphs for which that bound is off by a constant factor. Furthermore, we characterize trees with low hydra number, and give a lower bound for the hydra number of trees based on the number of vertices that are leaves in the tree obtained from T by deleting its leaves. This bound is sharp for some families of trees. We give bounds for the hydra number of complete binary trees and also discuss a related minimization problem.