Minimal k-arc Connected Graph

Abstract

A graph is k-arc-connected if it is necessary to remove at least k arcs in order to disconnect the graph. The paper solves the problem of determining the least 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+1)/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
Jan 01, 1971
Accession Number
AD0738032

Entities

People

  • D. R. Fulkerson
  • Lloyd Shapley

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Analogs
  • Communication Networks
  • Construction
  • Corporations
  • Elimination
  • Networks
  • Reliability

Readers

  • Graph Algorithms and Convex Optimization.