MINIMAL K-ARC-CONNECTED GRAPHS
RAND CORP SANTA MONICA CA
Pagination or Media Count:
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.
- Electrical and Electronic Equipment
- Theoretical Mathematics