Accession Number:

AD0738032

Title:

Minimal k-arc Connected Graph

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1971-01-01

Pagination or Media Count:

15.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE