A hypergraph is called box-Mengerian if the linear system A
x ≥ 1, x ≥ 0 is box-totally dual integral (box-TDI), where A is the edge-vertex incidence matrix of the hypergraph. Because it is NP-hard in general to recognize box-Mengerian hypergraphs, a basic theme in combinatorial optimization is to identify such objects associated with various problems. In this paper, we show that the so-called equitably subpartitionable (ESP) property, first introduced by Ding and Zang (2002) in their characterization of all graphs with the min-max relation on packing and covering cycles, turns out to be even sufficient for box-Mengerian hypergraphs. We also establish several new classes of box-Mengerian hypergraphs based on ESP property. This approach is of transparent combinatorial nature and is hence fairly easy to work with.
