MINIMAL K-ARC-CONNECTED GRAPHS

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.