Minimal k-arc Connected Graphs

A solution to 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 kn/2 arcs (for kn even) or (kn + 1)/2 arcs (for kn odd). (A linear graph is k-arc-connected if it is necessary to remove at least k arcs in order to disconnect the graph.) The results of this study are applicable to the problem of synthesizing minimum cost, "k-reliable" communication networks.

Note: This paper was written in 1961 (P-2371) but never published because the authors became aware that Harary was preparing a paper solved the more general problem of determining the least number of arcs required for k-arc-connectivity. Harary's paper later appeared under the title "The Maximum Connectivity of a Graph" in Proc. Nat. Acad. Sci. 48 (1962), 1142-1146. The authors of the present paper feel that the method of proof, which is quite different from Harary's proof of the more general result, may be of some interest.