MINIMAL K-ARC-CONNECTED GRAPHS

Abstract

A linear graph is k-arc-connected if it is necessary to remove at least k arcs in order to disconnect the graph. This paper solves the problem of determining the fewest number of arcs required in a k-arc-connected graph on n nodes by describing constructions that produce such graphs having kn/2 arcs (for kn even) or kn + l/2 arcs (for kn odd). These results have application to the practical problem of synthesizing minimum cost, 'k-reliable' communication networks.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 12, 1961
Accession Number
AD0636037

Entities

People

  • D. R. Fulkerson
  • Lloyd Shapley

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Analogs
  • California
  • Communication Networks
  • Construction
  • Corporations
  • Elimination
  • Literature
  • Microfiche
  • Networks
  • Reliability
  • Transitions

Readers

  • Graph Algorithms and Convex Optimization.