Totally unimodular Leontief directed hypergraphs
| Autor: | Peh H. Ng, Collette R. Coullard |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
Discrete mathematics
Class (set theory) Numerical Analysis Property (philosophy) Mathematics::Combinatorics Algebra and Number Theory Generalization Structure (category theory) Directed graph Combinatorics Unimodular matrix Computer Science::Discrete Mathematics Directed hypergraph Discrete Mathematics and Combinatorics Geometry and Topology Mathematics Incidence (geometry) |
| Zdroj: | Linear Algebra and its Applications. 230:101-125 |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/0024-3795(93)00369-b |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect