On the hydra number of disconnected graphs

The hydra number is a new graph parameter related to some minimization problem for Horn formulas in propositional logic. The hydra number of a graph G=(V,E) is the smallest number of hyperarcs of the form uv→w in a directed hypergraph H=(V,F) such that if uv∈E, then all vertices in V are reachable from {u,v} in H and if uv⁄∈E, then no other vertex apart from u and v is reachable from {u,v}. Reachability is defined by forward chaining, a standard marking procedure. In this paper we answer negatively a question posed in Sloan et al. (2017) concerning an anticipated formula for the hydra number of disconnected graphs. On the positive side, we show that the expression which appears in this formula is an upper bound for the hydra number of these graphs.