Totally unimodular Leontief directed hypergraphs

Collette R. Coullard, Peh H. Ng

    Research output: Contribution to journalArticlepeer-review

    2 Scopus citations

    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 languageEnglish (US)
    Pages (from-to)101-125
    Number of pages25
    JournalLinear Algebra and Its Applications
    Volume230
    DOIs
    StatePublished - 1995

    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.

    Fingerprint

    Dive into the research topics of 'Totally unimodular Leontief directed hypergraphs'. Together they form a unique fingerprint.

    Cite this