Minimal k‐arc connected graphs
- 1 January 1971
- Vol. 1 (1) , 91-98
- https://doi.org/10.1002/net.3230010108
Abstract
A 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 least 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 éven) or (kn+1) /2 arcs (for kn odd). These results have application to the practical problem of synthesizing minimum cost, “k‐reliable” communication networks.Keywords
This publication has 3 references indexed in Scilit:
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956
- Congruent Graphs and the Connectivity of GraphsAmerican Journal of Mathematics, 1932