Abstract
A Leontief directed hypergraph is a generalization of a directed graph, where arcs have multiple (or no) tails and at most one head. We define a class of Leontief directed hypergraphs via a forbidden structure called an odd pseudocycle. We show that the vertex-hyperarc incidence matrices of the hypergraphs in this class are totally unimodular. Indeed, we show that this is the largest class with that property. We define two natural subclasses of this class (one obtained by forbidding pseudocycles and the other obtained by forbidding pseudocycles and the so-called doublecycles), and we describe some structural properties of the bases and circuits of the members of these classes. We present examples of Leontief directed hypergraphs that are graphic, cographic, and neither graphic nor cographic.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 101-125 |
| Number of pages | 25 |
| Journal | Linear Algebra and Its Applications |
| Volume | 230 |
| DOIs | |
| State | Published - 1995 |
| Externally published | Yes |
Bibliographical note
Funding Information:* Research partially supported by the Office of Naval Research under University Research Initiative grant N00014-86-K-0689 at Purdue University and by the National Science Foundation under Presidential Young Investigators grant DDM-8957880. t Research partially supported by the Purdue Research Foundation under David Ross Fellowship 690-1287-1524 at Purdue University and the National Science Foundation under (C.R. Coullard's) Presidential Young Investigators grant DDM-8957880.