Optimally Invulnerable Directed Communication Networks

Abstract

Algorithms are given to synthesize optimally invulnerable directed graphs with an arbitrary number of vertices and a minimum number of branches. We give a decomposition of these graphs into a class of subgraphs called step- <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</tex> cycles, of which a directed Hamilton cycle is a special case. The use of this property in simultaneous <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</tex> commodity flows is demonstrated.