Analysis of minimal path routing schemes in the presence of faults

An ordered generating set of a group is hierarchical when the group generated by the first k generators is a proper subgroup of the group generated by the first k+1 for each k. Hierarchical Cayley graphs were introduced by Akers and Krishnamurthy as an interesting model to build symmetrical networks. In this paper the connectivity of hierarchical Cayley digraphs is studied, and it is shown that they have maximum connectivity except in a special case. An example of this exceptional case is given. The result generalizes similar statements of Godsil, Akers and Hamidoune.