SUBGRAPHS OF BIPARTITE AND DIRECTED GRAPHS

Abstract

The main theorem of this study provides necessary and sufficient conditions for a locally finite bipartite graph to have a subgraph whose valences lie in prescribed intervals. The theorem is applied to the study of integer-valued flows in locally finite directed graphs. In particular, generalizations of the max-flow min-cut theorem and the circulation theorem are obtained. The axiom of choice is assumed throughout.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1968
Accession Number
AD0668421

Entities

People

  • D. R. Fulkerson
  • Jon Folkman

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Air Force
  • Combinatorial Analysis
  • Families (Human)
  • Graph Theory
  • Inequalities
  • Intervals
  • Mathematics
  • Network Science
  • Numbers
  • Operations Research
  • Real Numbers
  • United States

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.