Accession Number:

AD0636037

Title:

MINIMAL K-ARC-CONNECTED GRAPHS

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1961-07-12

Pagination or Media Count:

14.0

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 kn2 arcs for kn even or kn l2 arcs for kn odd. These results have application to the practical problem of synthesizing minimum cost, k-reliable communication networks.

Subject Categories:

  • Electrical and Electronic Equipment
  • Theoretical Mathematics
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE