Premium
Minimal k‐arc connected graphs
Author(s) -
Fulkerson D. R.,
Shapley L. S.
Publication year - 1971
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230010108
Subject(s) - arc (geometry) , combinatorics , graph , mathematics , strongly connected component , computer science , discrete mathematics , geometry
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.