SUBGRAPHS OF BIPARTITE AND DIRECTED GRAPHS

Abstract

The main theorem of this memorandum provides necessary and sufficient conditions in order that a locally finite bipartite graph have a subgraph whose valences lie in prescribed intervals. This 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 of the circulation theorem are obtained. The axiom of choice is assumed throughout.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1965
Accession Number
AD0693568

Entities

People

  • D. R. Fulkerson
  • Jon Folkman

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Air Force
  • Corporations
  • Graph Theory
  • Inequalities
  • Intervals
  • Mathematics
  • Numbers
  • Operations Research
  • Real Numbers
  • Topology
  • Translations

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.